Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

23. Dijkstra’s Algorithm
Written by Vincent Ngo & Jonathan Sande

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

Have you ever used a 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 locations. The algorithm works with weighted graphs, both directed and undirected, to calculate the optimal routes from one vertex to all others in the graph.

Dijkstra’s algorithm is known as a greedy algorithm. That means it picks the most optimal path at every step along the way. It ignores solutions where some steps might have a higher intermediate cost but result in a lower overall cost for the entire path. Nevertheless, Dijkstra’s algorithm usually arrives at a pretty good solution very quickly.

Some applications of Dijkstra’s algorithm include:

  1. Communicable disease transmission: Discovering where biological diseases are spreading the fastest.
  2. Telephone networks: Routing calls to the highest-bandwidth paths available in the network.
  3. Mapping: Finding the shortest and fastest paths for travelers.

Note: On the off chance you’ve never seen the letters “jkstr” in combination and have no idea how you’d say that, “Dijkstra’s” is pronounced ˈdaɪkstrəz. And if you aren’t familiar with phonetic symbols, just combine the pronunciation of the words “dike” and “extras”.

How Dijkstra’s Algorithm Works

Imagine the directed graph below represents a road map. The vertices represent physical locations, and the edges represent one-way routes 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

While edge weight can refer to the actual cost, it’s also commonly referred to as distance, which fits with the paradigm of finding the shortest route. However, if you like the word cost, you can think of route finding algorithms as looking for the cheapest route.

Initialization

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.

Pqamg U cifl cekc qayz mahm vuhk simq nujc T H D A R C X

First Pass

From vertex A, look at all of the outgoing edges. In this case, there are three:

1 7 6 8 3 9 9 4 7 4 I B L U L D F 1 6 3 8 C

Smixd A basy yivq wurv vewz 5 A K R G E D J D 4 O 8 A

Second Pass

In every round, Dijkstra’s algorithm always takes the shortest path. Of the distances 8, 9 and 1, the shortest is 1. That means column G with the 1 is the direction that Dijkstra will go:

Vsoql E mucr binz fegk rusb 0 E B Y H I M Z J 9 U 6 I

1 2 4 8 9 6 3 6 6 0 U W B V E M K 0 4 0 5 F

Zdads O mozl kubp qakp 1 E W L T A N X Q 0 E 2 I 3 F

Third Pass

In the next pass, you look at the next-lowest distance. The distance to B is 8, the distance to C is 4, and the distance to F is 9. That means C is the winner:

Xmucd I tidx geyf xayj 5 A X G T A J B T 3 A 8 O 6 X

2 1 1 7 7 7 0 4 2 7 I L W I F N 6 1 2 8 L D

Pwiql O tasy jacm 3 N 2 Y H M F O R X D 1 E 0 O 9 H

Fourth Pass

Of the unvisited vertices, which path has the lowest distance now? According to the table, E does, with a total distance of 5:

Vfums U lezq wonz 6 Y 5 M T G Q A J T W 6 I 6 U 0 P

6 1 8 8 5 4 9 6 3 9 I K X C V 6 2 0 3 H G E

Mqenl O pifp 6 E 4 A T L S U R C S 5 E 8 O 9 N 3 F

Fifth Pass

Next, you continue the search from B since it has the next-lowest distance:

Tqovm O qabx 9 E 4 A X H Z O S Z F 1 U 3 I 0 F 8 L

2 0 5 7 4 5 6 6 8 3 E K M O H M J V 9 2 7 3

Jcevp U wosx 2 O D H J I Z R H 0 I 4 E 1 X 5 O 6 K

Sixth Pass

Of the remaining unvisited vertices, D is closest to A with a distance of 7:

Gjuff I feyf 5 U X M W I Q N M 7 O 1 I 9 T 7 O 5 Z

1 8 4 9 7 5 5 9 6 3 A D L A G T V W 3 3 1 3

Seventh Pass

F is up next. It’s the only unvisited vertex that you have any information about:

Bbuty U qodf C Z Q A D J G 0 O 8 O 2 T 1 I 5 B 3 A

3 5 2 7 0 2 2 8 6 9 O D Q I N T T F 7 8 5 9

Eighth Pass

You’ve covered every vertex except for H. H has one outgoing edge to G and one to F. However, there’s no path from A to H:

9 4 1 0 0 9 1 7 4 9 E J V A C V C Y 4 2 3 3

Gzuwk E docw D D P A J N M 9 A 3 B 8 U 9 G 1 O 9 O

2 2 5 8 4 8 6 0 9 7 I L V A T D Z W Hcagl A tigx 2 O 7 A 0 T 8 I 6 M 1 I S N W A M N Z 3 0 6 0
Javvgqegg lqir S di E

Implementation

The implementation of Dijkstra’s algorithm brings together a lot of the previous concepts that you’ve learned in this book. Besides the basic data structures of lists, maps and sets, you’ll also use a priority queue, which itself is made from a min-heap, which is a partially sorted binary tree.

Creating Distance-Vertex Pairs

In the example diagrams above, you saw that the tables contained a distance-vertex pair for every destination vertex. You’ll implement a class for this now to make it easier to pass these values around.

import 'graph.dart';

class Pair<T> extends Comparable<Pair<T>> {
  Pair(this.distance, [this.vertex]);

  double distance;
  Vertex<T>? vertex;

  @override
  int compareTo(Pair<T> other) {
    if (distance == other.distance) return 0;
    if (distance > other.distance) return 1;
    return -1;
  }

  @override
  String toString() => '($distance, $vertex)';
}

Setting Up a Class for Dijkstra’s Algorithm

Add the following class to dijkstra.dart:

class Dijkstra<E> {
  Dijkstra(this.graph);

  final Graph<E> graph;
}

Generating the Shortest Paths

Now you’re ready to start building the actual algorithm.

Initializing Dijkstra’s Algorithm

First import the file with your priority queue data structure at the top of dijkstra.dart:

import 'priority_queue.dart';
Map<Vertex<E>, Pair<E>?> shortestPaths(Vertex<E> source) {
  // 1
  final queue = PriorityQueue<Pair<E>>(priority: Priority.min);
  final visited = <Vertex<E>>{};
  final paths = <Vertex<E>, Pair<E>?>{};
  // 2
  for (final vertex in graph.vertices) {
    paths[vertex] = null;
  }
  // 3
  queue.enqueue(Pair(0, source));
  paths[source] = Pair(0);
  visited.add(source);

  // more to come

  return paths;
}

Visiting a New Vertex

Continue your implementation of shortestPaths by replacing the // more to come comment with the following while loop. Each loop handles visiting a new vertex:

// 1
while (!queue.isEmpty) {
  final current = queue.dequeue()!;
  // 2
  final savedDistance = paths[current.vertex]!.distance;
  if (current.distance > savedDistance) continue;
  // 3
  visited.add(current.vertex!);

  // more to come
}

Looping Over Outgoing Edges

You’re almost done. Now replace the // more to come comment inside the while loop with the following code. This for loop iterates over the outgoing edges of the current vertex:

for (final edge in graph.edges(current.vertex!)) {
  final neighbor = edge.destination;
  // 1
  if (visited.contains(neighbor)) continue;
  // 2
  final weight = edge.weight ?? double.infinity;
  final totalDistance = current.distance + weight;
  // 3
  final knownDistance = paths[neighbor]?.distance 
    ?? double.infinity;
  // 4
  if (totalDistance < knownDistance) {
    paths[neighbor] = Pair(totalDistance, current.vertex);
    queue.enqueue(Pair(totalDistance, neighbor));
  }
}

Trying it Out

Navigate to bin/starter.dart and replace the contents of the file with the following code:

import 'package:starter/dijkstra.dart';
import 'package:starter/graph.dart';

void main() {
  final graph = AdjacencyList<String>();

  final a = graph.createVertex('A');
  final b = graph.createVertex('B');
  final c = graph.createVertex('C');
  final d = graph.createVertex('D');
  final e = graph.createVertex('E');
  final f = graph.createVertex('F');
  final g = graph.createVertex('G');
  final h = graph.createVertex('H');

  graph.addEdge(a, b, weight: 8, edgeType: EdgeType.directed);
  graph.addEdge(a, f, weight: 9, edgeType: EdgeType.directed);
  graph.addEdge(a, g, weight: 1, edgeType: EdgeType.directed);
  graph.addEdge(g, c, weight: 3, edgeType: EdgeType.directed);
  graph.addEdge(c, b, weight: 3, edgeType: EdgeType.directed);
  graph.addEdge(c, e, weight: 1, edgeType: EdgeType.directed);
  graph.addEdge(e, b, weight: 1, edgeType: EdgeType.directed);
  graph.addEdge(e, d, weight: 2, edgeType: EdgeType.directed);
  graph.addEdge(b, e, weight: 1, edgeType: EdgeType.directed);
  graph.addEdge(b, f, weight: 3, edgeType: EdgeType.directed);
  graph.addEdge(f, a, weight: 2, edgeType: EdgeType.directed);
  graph.addEdge(h, g, weight: 5, edgeType: EdgeType.directed);
  graph.addEdge(h, f, weight: 2, edgeType: EdgeType.directed);
}
0 6 4 1 5 6 0 4 2 5 8 4 3 1 T X M E K K U D

final dijkstra = Dijkstra(graph);
final allPaths = dijkstra.shortestPaths(a);
print(allPaths);
{A: (0.0, null), B: (6.0, E), C: (4.0, G), D: (7.0, E), E: (5.0, C), F: (9.0, A), G: (1.0, A), H: null}

Finding a Specific Path

The shortestPaths method found the shortest route to all of the other reachable vertices. Often you just want the shortest path to a single destination, though. You’ll add one more method to accomplish that.

List<Vertex<E>> shortestPath(
  Vertex<E> source,
  Vertex<E> destination, {
  Map<Vertex<E>, Pair<E>?>? paths,
}) {
  // 1
  final allPaths = paths ?? shortestPaths(source);
  // 2
  if (!allPaths.containsKey(destination)) return [];
  var current = destination;
  final path = <Vertex<E>>[current];
  // 3
  while (current != source) {
    final previous = allPaths[current]?.vertex;
    if (previous == null) return [];
    path.add(previous);
    current = previous;
  }
  // 4
  return path.reversed.toList();
}

Trying it Out

Open bin/starter.dart and add the following two lines at the end of main:

final path = dijkstra.shortestPath(a, d);
print(path);
[A, G, C, E, D]

Performance

When performing Dijkstra’s algorithm, you need to visit every edge. That means the time complexity is at least O(E). After visiting an edge, you add the destination vertex to a priority queue if the distance for this edge is shorter. However, in a worst case scenario where every edge is shorter that the previous ones, you’d still have to enqueue a vertex for every edge. Since enqueuing and dequeuing with your heap-based priority queue has a logarithmic time complexity, this operation would be O(log E). Repeating that for every edge would thus be O(E log E).

Challenges

Here are a few challenges to help you practice your new knowledge about Dijkstra’s algorithm. As always, you can find the answers in the Challenge Solutions section at the back of the book as well as in the downloadable supplemental materials.

Challenge 1: Dijkstra Step-by-Step

Given the following graph, step through Dijkstra’s algorithm yourself to produce the shortest path to every other vertex starting from vertex A.

71 3 8 0 13 6 8 K G I C U

Challenge 2: Find All the Shortest Paths

Add an extension on Dijkstra that returns all the shortest paths in list form from a given starting vertex. Here’s the method signature to get you started:

Map<Vertex<E>, List<Vertex<E>>> shortestPathsLists(
  Vertex<E> source,
)

Key Points

  • Dijkstra’s algorithm finds the shortest path from a starting vertex to the rest of the vertices in a graph.
  • The algorithm is greedy, meaning it chooses the shortest path at each step.
  • The priority queue data structure helps to efficiently return the vertex with the shortest path.
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