singleSourceShortestPaths static method

Map singleSourceShortestPaths(dynamic graph, dynamic s, dynamic end)

Implementation

static Map singleSourceShortestPaths(graph, s, end) {
  /// Predecessor map for each node that has been encountered.
  /// node ID => predecessor node ID
  var predecessors = {};

  /// Costs of shortest paths from s to all nodes encountered.
  /// node ID => cost
  var costs = {};
  costs[s] = 0;

  /// Costs of shortest paths from s to all nodes encountered; differs from
  /// `costs` in that it provides easy access to the node that currently has
  /// the known shortest path from s.
  var open = PriorityQueue();
  open.add(s, 0);

  var closest,
      u,
      costOfSToU,
      adjacentNodes,
      costOfE,
      costOfSToUPlusCostOfE,
      costOfSToV,
      firstVisit;
  while (!open.empty()) {
    /// In the nodes remaining in graph that have a known cost from s,
    /// find the node, u, that currently has the shortest path from s.
    closest = open.pop();
    u = closest?["value"];
    costOfSToU = closest["cost"];

    /// Get nodes adjacent to u...
    adjacentNodes = graph[u] ?? {};

    /// ...and explore the edges that connect u to those nodes, updating
    /// the cost of the shortest paths to any or all of those nodes as
    /// necessary. v is the node across the current edge from u.
    (adjacentNodes as Map).forEach((v, value) {
      if (adjacentNodes?[v] != null) {
        /// Get the cost of the edge running from u to v.
        costOfE = adjacentNodes[v];

        /// Cost of s to u plus the cost of u to v across e--this is *a*
        /// cost from s to v that may or may not be less than the current
        /// known cost to v.
        costOfSToUPlusCostOfE = costOfSToU + costOfE;

        /// If we haven't visited v yet OR if the current known cost from s to
        /// v is greater than the new cost we just found (cost of s to u plus
        /// cost of u to v across e), update v's cost in the cost list and
        /// update v's predecessor in the predecessor list (it's now u).
        costOfSToV = costs[v];
        firstVisit = costs[v] == null;
        if (firstVisit || costOfSToV > costOfSToUPlusCostOfE) {
          costs[v] = costOfSToUPlusCostOfE;
          open.add(v, costOfSToUPlusCostOfE);
          predecessors[v] = u;
        }
      }
    });
  }

  if (end != null && costs[end] == null) {
    // print('Could not find a path');
  }

  return predecessors;
}