Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 6 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 16 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 10 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 11 chapters
Show chapters Hide chapters

42. Dijkstra’s Algorithm
Written by Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, 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:

  1. Communicable disease transmission: Discover where biological diseases are spreading the fastest.
  2. Telephone networks: Routing calls to highest-bandwidth paths available in the network.
  3. 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.

3 9 2 8 2 1 1 3 1 8 5 2 3 1 H G C E B F A D

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

3 9 2 8 2 1 1 3 1 8 5 2 3 1 A H F B D E C G 8 A 9 A 1 A nil nil nil nil B C D E F G H Start A

Second pass

8 A 9 A 1 A nil nil nil nil B C D E F G H Start A

5 2 3 3 3 0 3 9 7 7 8 5 0 3 E N G S F A B B Yquxh E 6 O 0 I xaz zup voj zex 7 U 8 U qir fuh feg 0 X 1 A 9 O R D P W I W W W

Third pass

Start A 8 A 9 A nil nil nil nil 8 A 9 A nil nil nil 4 G 1 A 1 A B G C D E F G H

5 7 8 3 0 8 0 2 5 8 0 7 4 9 E M W N V E Q Ybisg U 2 E 0 E zal guw dev gas 4 A 7 I nix viw pis 9 M 3 D 2 E 3 A 5 C 2 O 2 H yok nov 5 A X G K K T A W B Q Y

Fourth pass

Start A 8 A 9 A nil nil nil nil 8 A 9 A nil nil nil 4 G 4 G 1 A 1 A 7 C 9 A 5 C nil nil 1 A B G C C D E F G H

2 5 7 3 1 6 0 4 4 9 4 0 5 3 I C M N S K Lsejh U 4 I 4 U qip pad pah mew 4 A 4 I tuk sof wuf 7 N 4 B 4 U 4 A 1 Z 3 I soh moh 9 A 0 E 2 I 8 I noq 7 T 8 I 9 L 9 X J R N U V J U P M J P A

Fifth pass

Start A 8 A 9 A nil nil nil nil 8 A 9 A nil nil nil 4 G 4 G 1 A 1 A 7 C 9 A nil nil 1 A 6 E 9 A 7 E nil 4 G 1 A 5 C 5 C B G C E C D E F G H

Bkuvt A 3 A 8 O voy lul hap bak 7 O 9 I zuf dov wit 0 N 8 C 3 E 6 U 7 R 7 A mas woj 5 U 3 E 6 U 5 E sut 2 N 1 U 5 Q 8 U 8 E cib 3 A 4 Q 1 A 2 T 8 P W P G O B C R U J X P 5 8 5 0 4 5 6 3 5 0 7 9 9 6 A V C N Z T C I

Sixth pass

Start A 8 A 9 A nil nil nil nil 8 A 9 A nil nil nil 4 G 4 G 1 A 1 A 7 C 9 A nil nil 1 A 6 E 9 A 7 E nil 4 G 1 A 5 C 9 A 7 E nil 6 E 4 G 1 A 5 C 5 C B G C E B C D E F G H

6 9 2 4 2 4 8 6 6 2 1 8 2 5 O F B B B O P X Hhakz E 9 O 6 U dab gob pim keg 0 U 8 A huz sik zux 5 M 4 R 1 I 2 E 1 X 7 A 8 U 4 E cew duh gez 5 O 2 A 4 A 1 I 3 O 2 U 8 I vor 3 G 2 B 3 H 6 I 9 E 6 I 0 A 8 P 2 L 3 N 4 X Q K J U G P R R U K C L xar

Seventh pass

Start A 8 A 9 A nil nil nil nil 8 A 9 A nil nil nil 4 G 4 G 1 A 1 A 7 C 9 A 7 E 9 A nil nil nil 1 A 6 E 6 E 6 E 9 A 9 A 7 E nil 4 G 4 G 4 G 7 E 1 A 1 A 1 A 5 C 5 C 5 C 5 C B G C E B D C D E F G H nil

Dfars U 7 E 9 U bun guh quc dob 7 U 9 I xiq hag piq 1 L 3 Q 0 O 3 E 1 F 3 E 1 E 7 O toy fad vud gub 8 U 5 U 7 U 6 I 0 O 8 A 2 A 5 U nof 6 X 9 M 8 X 6 B 6 I 6 U 7 A 1 O 7 A 8 O 8 X 5 X 0 T 2 Q 7 E 2 V K G T E V T N F W I P C S 2 2 9 3 1 0 6 0 7 0 8 9 3 4 A X J Z E T X W dot

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.

Gceqv I 5 O 4 O lan sis kun fas 6 I 4 O fax sit rec 1 V 9 C 8 A 5 O 5 L 3 I 3 I 2 I bat vez guy lez 9 U 4 E 7 E 5 O 0 E 2 O 6 O 1 A hol 3 J 4 Q 8 W 4 H 5 E 2 A 8 A 3 A 3 O 8 E 4 R 4 X 3 X 9 L 2 U 0 Y B R S U G F G V F E F T M 2 3 2 8 5 3 3 4 4 4 3 8 9 2 O B R J A J F D qox

Vmikq I 0 I 0 V 4 O 7 I 2 U vix bud cic not faj hod xid son 3 I 9 I puc duh ned 9 X 3 Y 8 N 0 O 1 I 2 I 5 A qus xit 1 C 3 C 9 S 7 E 1 U 2 E 8 C 6 F 4 Y 0 E 3 O 5 E 6 U 9 E 0 O 5 A 1 A 1 U 1 O 6 S 2 A 7 G R W H E J T K Z N U K C R 0 5 7 1 7 7 1 0 9 9 4 9 6 7 M M A E P D J L

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
}

public class Dijkstra<T: Hashable> {

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

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

Helper methods

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

Tracing back to the start

C to G to A G 3 9 2 8 2 1 1 3 1 8 5 2 3 1 H C E D B A F 

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
}

Calculating total distance

Total distance = 4 A G 3 1 C 

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
}

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
}

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

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

Trying out your code

3 9 2 8 2 1 1 3 1 8 5 2 3 1 H G C E B F A D 

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)")
}
Q 9 4 1 6 2 8 7 6 0 9 1 3 1 8 N Y A X H U V 

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.

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!
41. Depth-First Search Challenges
43. Dijkstra’s Algorithm Challenges
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.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now