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 tentative distance when weights are nonnegative. A min-heap avoids scanning every unvisited vertex. A cheaper route may add another heap entry rather than updating an old one.

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.

distance := []int{0, 7, 2}
u, v, weight := 2, 1, 1
candidate := distance[u] + weight
if candidate < distance[v] {
	distance[v] = candidate
}
oldOffer := 7
fmt.Println(distance)                // [0 3 2]
fmt.Println(oldOffer != distance[1]) // true: skip that stale heap offer.

Settling distances needs nonnegative edges

Discard stale entries whose distance no longer equals the current best. Zero edges are valid; negative edges invalidate the settlement proof. Validate all edges, including unreachable components. This algorithm minimizes path cost, not total network connection cost. Build private working state. The Go API uses nil for absence and assumes finite cost arithmetic fits int.

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.

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