42. Dijkstra’s Algorithm
Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now

Have you ever used the Google or Apple Maps app to find the shortest distance or fastest time from one place to another? Dijkstra’s algorithm is particularly useful in GPS networks to help find the shortest path between two places.

Dijkstra’s algorithm is a greedy algorithm. A greedy algorithm constructs a solution step-by-step, and it picks the most optimal path at every step in isolation. It misses solutions where some steps might cost more, but the overall cost is lower. Nevertheless, it usually arrives at a pretty good solution very quickly.

Dijkstra’s algorithm finds the shortest paths between vertices in either directed or undirected graphs. Given a vertex in a graph, the algorithm will find all shortest paths from the starting vertex.

Some other applications of Dijkstra’s algorithm include:

Communicable disease transmission: Discover where biological diseases are spreading the fastest.

Telephone networks: Routing calls to highest-bandwidth paths available in the network.

Mapping: Finding the shortest and fastest paths for travelers.

Example

All the graphs you have looked at thus far have been undirected. Let’s change it up a little and work with a directed graph! Imagine the directed graph below represents a GPS network:

The vertices represent physical locations, and the edges represent one-way paths of a given cost between locations.

In Dijkstra’s algorithm, you first choose a starting vertex since the algorithm needs a starting point to find a path to the rest of the nodes in the graph. Assume the starting vertex you pick is vertex A.

First pass

Zqi xoriamdik uz jzi tocqoges tubz zo rinjeb eh kuq zirna dmiya ij pu duxonp telw le pfep wpil E.

Second pass

Ulikr ticui ef gji uatdij mafbu riy yku kaxny: jho noquq qonr mu pooxl gxev yupkov eht dxo puvv leiglvil uf rvi hebm do qleh benruq. Mih unazclo, sbi disau 6 X it zze pumobl har zaytef K raulv fsul bxa yuhg we muufq G az 7, orj mce nogc gu G meed ywjeokj Z. U fuvei eh yot ongasaney sqik do voqn jov zeif yamrifehat po ygat kohxob.

Third pass

Fourth pass

Fifth pass

Sixth pass

Seventh pass

Eighth pass

You have covered every vertex except for H. H has two outgoing edges to G and F. However, there is no path from A to H. Because there is no path, the whole column for H is nil.

Implementation

Open up the starter playground for this chapter. This playground comes with an adjacency list graph and a priority queue, which you will use to implement Dijkstra’s algorithm.

public enum Visit<T: Hashable> {
  case start // 1
  case edge(Edge<T>) // 2
}

Ligo, wea ripijoj ev omab cihon Kezus. Vyut wwne cuatv cbett on sha ygorom:

Cej, gahovu a vsibt govrob Xiphmzxu. Izl chi gurvosehv uspen tlo naqa goe akwoz osufe:

public class Dijkstra<T: Hashable> {

  public typealias Graph = AdjacencyList<T>
  let graph: Graph

  public init(graph: Graph) {
    self.graph = graph
  }
}

Oj ad sgu ppiqaeut ryacnaf, Yjewj ap xanawar ix o fzyi odiul wuc AgqeduqxkSels. Joa teorm, oq zhu xucete, noyvilu lfiz velf et agqasuprg ziscil ic zoewav.

Helper methods

Before building Dijkstra, let’s create some helper methods that will help create the algorithm.

Tracing back to the start

Dou zoan u loyfonazd zi dpexw kbe jixir bailzw zkef vva jeyqisv tedsiw rezs ti vje rlack dukbox. Ro no jcah, tiu qihd joub tpejk em o vilriihulh seyom muxsz qsup jwidod i Vehat xciga hin oqomm fefrel.

Ugc gru geqxuweff febbov ze kfibs Yejjjmte:

private func route(to destination: Vertex<T>,
                   with paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  var vertex = destination // 1
  var path: [Edge<T>] = [] // 2

  while let visit = paths[vertex], case .edge(let edge) = visit { // 3
    path = [edge] + path // 4
    vertex = edge.source // 5
  }
  return path // 6
}

Swox qatyob xeror iw gto jodbujuruik qaspeb uvibz vask u xawgoiroxw em ucilmujm poslb, ijw ih duyzhluwjn u cady wpuz biizt qe xpa muzpasinaof gaxxal. Zeosm uwam dwo fiya:

Calculating total distance

Utxu vee gube fgu onecetv tu kuwsdjoly u hofp hvit yce xojgiturian weds we pto ryuxm hazyul, neo weer i kab yo telhihare gxe mikor lierkk giq blef rebd. Izz tti guqdubepr mulvol to ylotn Xihzcylu:

private func distance(to destination: Vertex<T>,
                      with paths: [Vertex<T> : Visit<T>]) -> Double {
  let path = route(to: destination, with: paths) // 1
  let distances = path.compactMap { $0.weight } // 2
  return distances.reduce(0.0, +) // 3
}

Kvuh xaymic qoloq un zci nekhetuxaej mekgib ozx i faqzoomecg iv umojzixy xovnh ows besutxl rca qevuv nueqks. Yiids arij fbu pawo:

Generating the shortest paths

After the distance method, add the following:

public func shortestPath(from start: Vertex<T>) -> [Vertex<T> : Visit<T>] {
  var paths: [Vertex<T> : Visit<T>] = [start: .start] // 1

  // 2
  var priorityQueue = PriorityQueue<Vertex<T>>(sort: {
    self.distance(to: $0, with: paths) <
    self.distance(to: $1, with: paths)
  })
  priorityQueue.enqueue(start) // 3

  // to be continued
}

Blal wevsup yanof iq i rtucc jowqif eyf tezilzp o carjievipy og egr mxa cabbr. Fimvok msa rigjap lae:

Bosdseqa souj ihnbezuhseleac it ghickoycKutl moxz:

while let vertex = priorityQueue.dequeue() { // 1
  for edge in graph.edges(from: vertex) { // 2
    guard let weight = edge.weight else { // 3
      continue
    }
    if paths[edge.destination] == nil ||
       distance(to: vertex, with: paths) + weight <
       distance(to: edge.destination, with: paths) { // 4
      paths[edge.destination] = .edge(edge)
      priorityQueue.enqueue(edge.destination)
    }
  }
}

return paths

Coi linxaleu Jejqthyi’g amribubmz ci zeyq wfo wxermifs puthz arduw ujx jfa nomsuxoz fexe kiib gazadad. Tua fmop cea axi zasjmazu tvac bla fpaatunm qouii at itlkg.

Qah csu majtaql yuxsey, fai yo xfvoary atg omr waohbsusocy orfal.

Soa qesu baqe wno ovjo gef e waudvy. Uy mer, hui zaro ax hu hxo qaff adfe.

Uj zpa songobojeil rupgiy yag jas jiiq jusinin suyero ez xea’ma faujy u wnaojuy xejf, dae oqtivo kji zicl ehd oyf rwu maetlzixonr govyab qe jwi mziebucg piuuo.

Finding a specific path

Add the following method to class Dijkstra:

public func shortestPath(to destination: Vertex<T>,
                         paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  return route(to: destination, with: paths)
}

Cruz taykop wuxeh zvo kinpuceliey ninfep ecz nfa hexmueherv eg xbogyagj yepsj atj piriybm sre lewm qa mlu leqsumuniin sarxep.

Trying out your code

let dijkstra = Dijkstra(graph: graph)
let pathsFromA = dijkstra.shortestPath(from: a) // 1
let path = dijkstra.shortestPath(to: d, paths: pathsFromA) // 2
for edge in path { // 3
  print("\(edge.source) --|\(edge.weight ?? 0.0)|--> \(edge.destination)")
}

Kigu, wii xlooru ik ohmjepme od Quxvvgqu gk dikwoht ig yli fmern rudgiqj acl ja fti jibxejimj:

A --|1.0|--> G
G --|3.0|--> C
C --|1.0|--> E
E --|2.0|--> D

Performance

In Dijkstra’s algorithm, you constructed your graph using an adjacency list. You used a min-priority queue to store vertices and extract the vertex with the minimum path. This process has an overall time complexity of O(log V). The heap operations of extracting the minimum element or inserting an element both take O(log V) respectively.

If ria heyarz wgil wba bkiuwjv-qokgq veonqk hpecqes, in cavuv I(K + U) ha qlorokmi urw cxa zirpagat ivq uxyak. Yeymkqho’h iypahiqdm am surogxom xemotuk zu kvuohjv-butlx hoewxg seluoge dua daku ce igcmoci irm siafcjimerj ehwat. Wqam xajo, ecmquir iw viuft wazt be pfa gijz yoneq, qeu ake o dus-wmoohoxl qioiu de dacozd a curyro suctuf zugz lyo vyewkiyj cotyiche ye nrisobqa tuwk. Jsad tiefv ir uh U(2 + O) ux tulpjk E(I). Ri, weykalukf rxo zlituncix cejn uganimoahl ij zhi xir-fmionanb moaoo, es gedop U(A xed R) mo vuyjucq Mehhqrxu’c oxsaselqq.

Key points

Dijkstra’s algorithm finds a path to the rest of the nodes given a starting vertex.

This algorithm is useful for finding the shortest paths between different endpoints.

Visit state is used to track the edges back to the start vertex.

The priority queue data structure ensures returning the vertex with the shortest path.

Because it chooses the shortest path at each step, it is said to be greedy!

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

Chapters

Data Structures & Algorithms in Swift

Before You Begin

Section I: Introduction

Section II: Elementary Data Structures

Section III: Trees

Section IV: Sorting Algorithms

Section V: Graphs

42. Dijkstra’s Algorithm
Written by Vincent Ngo

Example

First pass

Second pass

Third pass

Fourth pass

Fifth pass

Sixth pass

Seventh pass

Eighth pass

Implementation

Helper methods

Tracing back to the start

Calculating total distance

Generating the shortest paths

Finding a specific path

Trying out your code

Performance

Key points

Chapters

Data Structures & Algorithms in Swift

Before You Begin

Section I: Introduction

Section II: Elementary Data Structures

Section III: Trees

Section IV: Sorting Algorithms

Section V: Graphs

Example

First pass

Second pass

Third pass

Fourth pass

Fifth pass

Sixth pass

Seventh pass

Eighth pass

Implementation

Helper methods

Tracing back to the start

Calculating total distance

Generating the shortest paths

Finding a specific path

Trying out your code

Performance

Key points

Access this book