23 Chapter 23 Solutions

Solution to Challenge 1

These are the shortest paths from A to the following vertices:

• Path to B: A - (1) - B
• Path to C: A - (1) - B - (8) - C
• Path to D: A - (1) - B - (9) - D
• Path to E: A - (1) - B - (8) - C - (2) - E

Solution to Challenge 2

To get the shortest paths from the source vertex to every other vertex in the graph, use the following extension on Dijkstra:

extension ShortestPaths<E> on Dijkstra<E> {
  Map<Vertex<E>, List<Vertex<E>>> shortestPathsLists(
    Vertex<E> source,
  ) {
    // 1
    final allPathsLists = <Vertex<E>, List<Vertex<E>>>{};
    // 2
    final allPaths = shortestPaths(source);
    // 3
    for (final vertex in graph.vertices) {
      final path = shortestPath(
        source,
        vertex,
        paths: allPaths,
      );
      allPathsLists[vertex] = path;
    }
    return allPathsLists;
  }
}

This is how it works:

1. The map stores the path to every vertex from the source vertex.
2. Perform Dijkstra’s algorithm to find all the paths from the source vertex.
3. For every vertex in the graph, generate the list of vertices that makes up the path.