dijkstraDistances function

List<double> dijkstraDistances(WeightedAdjacency graph, int source)

Returns shortest distances from source to all nodes; unreachable = infinity.

Implementation

List<double> dijkstraDistances(WeightedAdjacency graph, int source) {
  final List<double> dist = List.filled(graph.length, double.infinity);
  dist[source] = 0;
  final List<int> heap = <int>[source];
  while (heap.isNotEmpty) {
    heap.sort((int a, int b) => dist[a].compareTo(dist[b]));
    final int u = heap.removeAt(0);
    for (final (int v, double w) in graph[u]) {
      final double d = dist[u] + w;
      if (d < dist[v]) {
        dist[v] = d;
        if (!heap.contains(v)) heap.add(v);
      }
    }
  }
  return dist;
}