Java Dijkstra: non-negative routes and stale heap entries

Java 8+. The program uses only JDK classes and runs without a framework.

Distances and pending candidates have different lifetimes

A delivery planner needs the cheapest travel time from one depot to every reachable depot. The distance array stores the best known total. A priority queue orders pending candidates by that total so the smallest candidate can be examined next.

The program uses lazy queue updates: it inserts a new candidate when a shorter route is found instead of editing an older entry already in the heap. An old candidate can therefore remain pending after its distance has improved. The equality check against the distance array discards that stale entry before relaxing its outgoing roads.

Ordinary BFS minimizes edge count, not total weight. A two-road journey can be cheaper than a direct road with a large travel time. Use BFS only when its unweighted cost model matches the problem.

Reject a cost model the proof does not support

Negative road weights are rejected by the Road constructor. Allowing a negative edge invalidates the greedy finalization argument; removing the validation does not extend this implementation to refunds or negative adjustments. Choose a shortest-path algorithm that supports those weights.

Distances use long even though one road’s minutes use int. Before addition, the method checks whether the candidate total would overflow. Long.MAX_VALUE represents unreachable, so an exactly equal route cost is outside this representation’s finite-distance contract. A production API should expose reachability explicitly rather than print the sentinel as a valid journey.

Working program

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class DeliveryDistances {
    static class Road {
        final int depot, minutes;
        Road(int depot, int minutes) {
            if (minutes < 0) throw new IllegalArgumentException("Negative travel time");
            this.depot = depot; this.minutes = minutes;
        }
    }
    static class Candidate {
        final int depot;
        final long minutes;
        Candidate(int depot, long minutes) { this.depot = depot; this.minutes = minutes; }
    }
    static long[] shortest(List<List<Road>> roads, int source) {
        if (source < 0 || source >= roads.size()) throw new IllegalArgumentException("Unknown source");
        long[] distance = new long[roads.size()];
        Arrays.fill(distance, Long.MAX_VALUE);
        distance[source] = 0;
        PriorityQueue<Candidate> pending = new PriorityQueue<>(Comparator.comparingLong(c -> c.minutes));
        pending.add(new Candidate(source, 0));
        while (!pending.isEmpty()) {
            Candidate current = pending.poll();
            if (current.minutes != distance[current.depot]) continue;
            for (Road road : roads.get(current.depot)) {
                if (road.depot < 0 || road.depot >= roads.size()) throw new IllegalArgumentException("Unknown destination");
                if (current.minutes > Long.MAX_VALUE - road.minutes) throw new ArithmeticException("Distance overflow");
                long improved = current.minutes + road.minutes;
                if (improved < distance[road.depot]) {
                    distance[road.depot] = improved;
                    pending.add(new Candidate(road.depot, improved));
                }
            }
        }
        return distance;
    }
    public static void main(String[] args) {
        List<List<Road>> roads = new ArrayList<>();
        for (int depot = 0; depot < 4; depot++) roads.add(new ArrayList<>());
        roads.get(0).add(new Road(1, 4)); roads.get(0).add(new Road(2, 10));
        roads.get(1).add(new Road(2, 3)); roads.get(1).add(new Road(3, 12));
        roads.get(2).add(new Road(3, 1));
        System.out.println(Arrays.toString(shortest(roads, 0)));
    }
}

Output

[0, 4, 7, 8]

Cost and failure boundaries

With adjacency lists and lazy candidates, the queue can retain O(e) entries for e edges. The total bound is O(v + (v+e) log(e+1)) work, with O(v+e) extra state in the worst case. This queue representation is why quoting only O(v) heap storage would be misleading.

The result contains distances only. Returning paths requires a predecessor array updated when a distance improves, followed by path reconstruction. Tests should include unreachable depots, zero-weight edges, parallel roads, cycles and a cheaper indirect journey that makes an older queue entry stale.

Common Mistakes

• Do not accept negative weights without changing the algorithm.
• Do not expand stale queue candidates as if they were current best routes.
• Do not mistake the unreachable sentinel for a finite distance.

Connect the contracts

Compare the boundary explained in Heap ordering and costs with the assumptions made by this program.

Compare the boundary explained in Reachability without weights with the assumptions made by this program.

Continue with range and graph boundaries

Continue with Java A* on a unit grid: an admissible Manhattan bound, Java Edmonds-Karp max flow: residual capacity and reverse edges.