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

Find cheapest directed routes when all edge weights are nonnegative. A discovered vertex can still receive a cheaper route before its best frontier entry is settled.

A shortest-hop traversal ignores weights, and marking a vertex final on discovery can preserve an expensive early route. A priority queue holds tentative costs; stale earlier entries are harmless only when explicitly rejected.

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.

Nonnegative weights make the cheapest frontier distance final when popped. A priority queue may retain an earlier, more expensive entry for the same vertex; discard it by comparing to the current best distance. Marking on discovery is incorrect. Final O((V+E) log(max(2,E))) time and O(V+E) space.

A queued distance can become obsolete after another path improves the current best value:

import java.util.*;

class Example {
    public static void main(String[] args) {
        record Visit(int vertex, long distance) {}
        long[] best = {0, 2};
        Visit queuedEarlier = new Visit(1, 10);
        assert queuedEarlier.distance() != best[queuedEarlier.vertex()];
        assert best[1] == 2;
    }
}

The distance-10 entry must not expand vertex 1 again as if it were current. This stale check does not validate the nonnegative-weight assumption: even an unreachable negative edge must be rejected by this exercise contract.

Settling distances needs nonnegative edges

Dijkstra fits nonnegative routing and cost frontiers where settling the cheapest candidate is safe. Negative edges break that settlement argument and require a different method, even without a negative cycle.

Directed weighted edges allow parallel edges, self-loops, and zero costs. Return minimum Long costs in vertex order and null for unreachable vertices. Reject n <= 0, invalid source/endpoints, and every negative edge weight, including unreachable ones.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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