criticalPathDistances function

List<double> criticalPathDistances(
  1. WeightedAdjacency graph,
  2. int start
)

Longest path from start to each node (DAG). Returns distances.

Implementation

List<double> criticalPathDistances(WeightedAdjacency graph, int start) {
  final List<double> dist = List.filled(graph.length, double.negativeInfinity);
  dist[start] = 0;
  final List<int> order = _topoOrder(graph);
  for (final int u in order) {
    if (dist[u] == double.negativeInfinity) continue;
    for (final (int v, double w) in graph[u]) {
      if (dist[u] + w > dist[v]) dist[v] = dist[u] + w;
    }
  }
  return dist;
}