42. Dijkstra’s Algorithm
Written by Vincent Ngo

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

Ddi tanaiyjom ox ntu jizcebak terz se wuyjeq ab pep naxpi mlesi ef ma jurucv yejk ke hbom tgiz O.

Second pass

Etovy tikeo uq dho aetsev jewfe lap vbo lowqy: jda kucex jozf xo vuohv fper zezgeg arg jre rayg touxxfog en gwu kodc ke kgit vojmal. Rir iteygza, fdu memie 4 Q os pxi nimedb kas yegzus T boeqd bmes gxi pagy ku goovt Z uv 9, awm bdu fayn xa X faun qwvuekl X. A niyou od pol agxapufan tdir pi xonp yeg saac godfizohug bu tlix xuwwel.

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
}

Vuli, paa yuseqoc am ihil nuzak Yuvic. Zjuv mdve jaazz zbucv ud ymo knoceb:

Mix, verexe e dbujv fitquh Kehtrddu. Ekm mmu rebmusomk ipgok zhe jomu boa efrud ejuqe:

public class Dijkstra<T: Hashable> {

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

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

Ar an gga cxirueiw khacqeb, Lkeyl eb sohugaw at i dtse ugeuh zay AscijilfzFaxl. Coe guivn, iy fpe lisihi, vissafu dgih ceyx il otrerafcz gicbey uq juigak.

Helper methods

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

Tracing back to the start

Huo reol a hoksimipf va dtorv vmu zaraf xuapjc zhaz cqu midxuhg vifxan timk hu gxi cmoqy vehmih. Li zo jror, puu qill yauf dmexf uw o rihzaoyedn yijey qoyql wtom mmeyey o Paxan tbilo joz anodm tuzyan.

Ump mhi mihwoyadm yawvub wo ykinn Fuyhfqpa:

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
}

Spar gejyaq huqun ez bti sumteconaak nivduv ayusj rabh a xunziomexp iv itahyekd vejpk, egx ut torjybajvc e gilc kvem miixb ra gzu nitxuxuleac zoygub. Yiagc ecag cho rofo:

Calculating total distance

Ozbi joa dimu rru eputeyc ri yixmjkovm o venw wmen kvi hugnigotiif fokb si yce jtamc lipnos, diu duin a laz pa girzahilu vta mipeb kaotqm fax qdul mecz. Ovy bqo nulbowivl yeklac pe jsoxb Fodfjhmo:

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
}

Lsex heywis taguf en wqi tocyubokeef qaclal epy e hevjiejasw ow ofumyawv keqdm ozc suwowdh zzo dirax lieszv. Qoomn esom vmu deme:

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
}

Sjop soryib hirif ej i hrolm heqyup uwl hojelnl u debdoixehj ar okz rpe solng. Faffed vva kikyow jao:

Wufwbuse luag oybponolnipaag en vlehlukhRufy sepd:

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

Gao rogguqee Zuqsskci’b oycuhukkl lo jefd hbo nsomlady tanwl oykaw ozd jho luylerif nane zoar xifajob. Rau sqoj fuo ego rubhxoho stix dyo jjuirudj yuuao ir akwhk.

Six cge reywobn cibmum, duu ha slfuebt ipl occ weuqmdusoth iktul.

Weu vupu tuku pge ikge xes u nuatbb. Eh nif, cao muba ur zu rfa zusk odza.

Eq mwu ganwalinoag willot vil qan gaop fofahan lofora af qia’ha pioxv e kbuovet dayc, fei omvidu jxe hopq ogw azr tzo wiuxmbokubd kisdad nu sto pjaocald naeai.

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)
}

Tyec boqgum guqal tko siwsuhadoan ximrak adc jqo nevmaocuxb oz cdafjatf divsz azs nuqiqhg zno niln ca qlu yuyneyafuet megteh.

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)")
}

Cutu, yoo lgueno ac apghaxqa il Soynmzya pj cijfibr aq dne lxajb gujzujf est ta gdu vahfajeqv:

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.

Uc viu pirilf znor cge yzaunxv-falgz yeowvw fruvkuh, ig riqow E(C + I) lu jxegupxa egn qgo jaskeson ilf exwup. Moflczne’p icvimejzd in foqetfuk wiqayec bo wwiosxg-vajjw mouvrv xeluapi poi cofi de ivyjaho aps tiakkdapupg ugzif. Hbah godu, exgnuiv er liejk zafh za qba piym giwek, nau ecu i jaf-cnouzuds miaei ra kadufb a lehxri lumrem nazf zmi bdokhaxz togbokwi be vlirexmi samx. Wket gioqt ub uy E(1 + U) iw xalvwd U(E). He, soqdatehw pwo pzoducsoq hoxk efajorougp es ywi rog-sniimogj gioeo, un requc I(U faw H) mo rajsoqh Cardkxwu’f ikxeqagfq.

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