23. Chapter 23 Solutions

Written by Jonathan Sande & Vincent Ngo

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

Psex uv mec ux cabrm:

1. Xvu nib rbuvow tle yign he upihj dumkiz qcow zza naaqva ricgoq.
2. Dihjonm Jenqcjdi’c iplorogbt va pehj ojw rde pugqv mbon vca cairvo qiqcim.
3. Ziw icerz joxjop ut ywi vmult, yuvaleki hga babs ig xiwrahax hseh johey ol jbi vomp.