dijkstra<T> function

Map<T, num> dijkstra<T>(Map<T, List<WeightedEdge<T>>> graph, T start)

Implementation

Map<T, num> dijkstra<T>(Map<T, List<WeightedEdge<T>>> graph, T start) {
  final Set<T> nodes = {...graph.keys};
  for (final neighbors in graph.values) {
    for (final e in neighbors) {
      nodes.add(e.source);
      nodes.add(e.target);
    }
  }

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

  final Set<T> visited = <T>{};

  while (visited.length < nodes.length) {
    // pick unvisited node with smallest distance
    T? u;
    num best = double.infinity;
    for (final n in nodes) {
      if (!visited.contains(n) && dist[n]! < best) {
        best = dist[n]!;
        u = n;
      }
    }
    if (u == null || dist[u] == double.infinity) break;
    visited.add(u);

    final List<WeightedEdge<T>> edgesFromU = graph[u] ?? <WeightedEdge<T>>[];
    for (final edge in edgesFromU) {
      if (edge.weight < 0) {
        throw ArgumentError('Dijkstra requires non-negative edge weights');
      }
      final alt = dist[u]! + edge.weight;
      if (alt < dist[edge.target]!) {
        dist[edge.target] = alt;
      }
    }
  }

  return dist;
}