bellmanFord<T> function

Map<T, num> bellmanFord<T>(
  1. Set<T> nodes,
  2. List<WeightedEdge<T>> edges,
  3. T start
)

Implementation

Map<T, num> bellmanFord<T>(Set<T> nodes, List<WeightedEdge<T>> edges, T start) {
  final Map<T, num> dist = {for (final n in nodes) n: double.infinity};
  dist[start] = 0;

  for (var i = 0; i < nodes.length - 1; i++) {
    var updated = false;
    for (final e in edges) {
      if (dist[e.source] != double.infinity) {
        final alt = dist[e.source]! + e.weight;
        if (alt < dist[e.target]!) {
          dist[e.target] = alt;
          updated = true;
        }
      }
    }
    if (!updated) break;
  }

  for (final e in edges) {
    if (dist[e.source] != double.infinity &&
        dist[e.source]! + e.weight < dist[e.target]!) {
      throw StateError('Graph contains a negative weight cycle');
    }
  }

  return dist;
}