shortestPaths method

Map<T, Iterable<T>> shortestPaths(T start)

Returns a map containing the shortest paths from start to each reachable vertex. The map keys represent the set of vertices reachable from start.

Implementation

Map<T, Iterable<T>> shortestPaths(T start) {
  final pathMap = <T, Iterable<T>>{};

  final tree = <Set<T>>[];
  for (final connected in edges(start)) {
    pathMap[connected] = ([connected]);
    if (connected != start) {
      // Do not follow self-loops.
      // Store first branches of tree.
      tree.add({connected});
    }
  }

  if (tree.isNotEmpty) {
    var startIndex = 0;
    var endIndex = 0;
    var length = tree.length;
    do {
      endIndex = tree.length;
      for (var i = startIndex; i < endIndex; ++i) {
        final path = tree[i];
        for (final vertex in edges(path.last)) {
          // Discard walks which reach the same (inner) vertex twice.
          // Note: Each path starts with [start] even though it is not
          // listed!
          if (path.contains(vertex) || path.contains(start)) {
            continue;
          } else {
            // Store path to new vertex.
            pathMap[vertex] ??= ([...path, vertex]);

            // Continue growing tree.
            tree.add({...path, vertex});
            length++;
          }
        }
      }
      startIndex = endIndex;
    } while (endIndex < length);
  }
  return pathMap;
}