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 settles the cheapest frontier distance, rather than the first edge that discovers a vertex. A later route can improve a discovered tentative cost. Heap entries contain a copied distance; when a popped entry no longer equals the current best, it is stale and must be skipped.

Replacing an expensive tentative route

From 0, roads to 1 and 2 cost 7 and 2; the road 2 → 1 costs 1. The heap first offers location 1 at cost seven, then improves it to three after processing 2. Leave the old offer in the heap if convenient, but skip it when popped because its cost no longer matches the current distance. Zero-cost edges are valid; negative ones break the settlement argument.

using Entry=std::pair<Int,Int>; // cost, vertex
std::priority_queue<Entry,std::vector<Entry>,std::greater<>> frontier;

Settling distances needs nonnegative edges

Nonnegative weights ensure a settled cheapest route cannot be improved through a more expensive unsettled frontier. A negative edge invalidates that proof, even when one example happens to work. Zero-cost cycles and parallel edges are valid; enqueue only strict improvements to avoid endless cycling. Optional distances represent unreachable vertices without arithmetic on infinity. The heap implementation uses O((V+E) log(V+E)) time and O(V+E) storage with lazy stale entries. Validate the complete graph before indexing or starting relaxation.

A lazy heap can retain O(E) improved offers, giving O(V+E log(E+2)) time with O(V+E) representation and frontier space. A dense-matrix implementation can instead use O(V²) time. These bounds do not justify negative weights; the nonnegative-edge proof is a separate requirement.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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