Dijkstra shortest paths

A delivery planner compares routes whose road segments take different amounts of time. One direct road can be slower than two short segments, so the fewest-hop answer from BFS isn't enough.

Dijkstra keeps the cheapest route found so far to each location and processes the smallest current offer next. A later discovery may improve an earlier offer; the priority queue must handle that without treating the old price as final.

Choosing routes by cost rather than hops

Dijkstra finds minimum weighted path costs when every edge has nonnegative cost. First discovery is tentative: a costly direct edge can be improved by a later route. The next vertex settled must have the globally cheapest frontier cost, not the next vertex discovered.

Enumerating simple paths is a useful small-input prototype but grows exponentially. A min-heap reuses the best tentative distances and prioritizes the next safe settlement.

Replacing an expensive tentative route

A heap entry stores a copied pair [cost, vertex]. Whenever relaxation improves a distance, insert a new entry. An older entry for the same vertex may remain in the heap; skip it when its copied cost no longer equals the current distance. Processing stale entries needlessly can repeat a large amount of work.

Nonnegative edges justify settling the minimum: passing through a more expensive unsettled frontier cannot create a cheaper route back to it. Negative weights invalidate that argument and are rejected. Zero edges, zero cycles and parallel edges are valid. Relax only a strict improvement so a zero-cost cycle cannot generate endless equal entries.

Use null for unreachable results and check it explicitly before arithmetic. Validate every edge before indexing adjacency, even edges in a component the source never reaches. A numeric min-heap needs an explicit comparator; arrays are not automatically ordered numeric tuples in JavaScript.

const tentative = [0, 10, 1];
const oldEntry = [10, 1];
tentative[1] = 2; // a cheaper route was discovered later
console.log(oldEntry[0] !== tentative[oldEntry[1]]); // true: this entry is stale

Settling distances needs nonnegative edges

With lazy heap entries, runtime is O(V+E log(E+1)) and storage O(V+E), including adjacency and stale frontier entries. This suits sparse nonnegative weighted graphs. BFS is simpler when every edge has equal unit weight; Bellman-Ford permits negative weights at a higher cost. The algorithm computes source distances, not a minimum spanning tree.

Recovering the delivery itinerary also needs predecessor information; distances alone do not list its roads.