dijkstraWithParents function
Returns (distances, parent array). The parent list entry at index i is the predecessor on shortest path from source. Audited: 2026-06-12 11:26 EDT
Implementation
(List<double> dist, List<int?> parent) dijkstraWithParents(WeightedAdjacency graph, int source) {
// Same as dijkstraDistances, but also records each node's predecessor so the
// actual shortest path (not just its length) can be reconstructed.
final List<double> dist = List.filled(graph.length, double.infinity);
final List<int?> parent = List.filled(graph.length, null);
// Guard a bad/empty source before indexing, matching dijkstraDistances.
if (source < 0 || source >= graph.length) return (dist, parent);
dist[source] = 0;
// Settled set guarantees termination (see dijkstraDistances); requires
// non-negative weights for correct results.
final List<bool> settled = List<bool>.filled(graph.length, false);
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);
if (settled[u]) continue;
settled[u] = true;
for (final (int v, double w) in graph[u]) {
if (settled[v]) continue;
final double d = dist[u] + w;
if (d < dist[v]) {
dist[v] = d;
// Record how we reached v so the path back to source can be traced.
parent[v] = u;
if (!heap.contains(v)) heap.add(v);
}
}
}
return (dist, parent);
}