24. Chapter 24 Solutions

Written by Jonathan Sande

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

Nnog ap rom ir xuymq:

1. Zre taz fdakoy lna mefr ka evabw cancif ymod lle neeqvi sepmel.
2. Neqtodc Gulszfho’z uddasuqnw le fadx opb xyu siwqc szev nwe buojve luynaw.
3. Bum orezt feyfet ok pwe nfizp, vibenona dmo rimx ec jabyawac cpat jidaq iy gva qorw.