A mesh router picks the “shortest” path between two services. Edges are p95 latency in milliseconds. The first version used a queue: dequeue a hop, enqueue unseen neighbors, stop at the destination. That is BFS. It returned the path with two hops. Those hops were 400 ms and 350 ms. A three-hop path of 8 ms each sat in the same graph. Nobody “chose a slow algorithm.” They ran an unweighted procedure on weighted edges.
Dijkstra always settles the unsettled vertex with the smallest known distance — and that distance is final when every edge weight is non-negative. The layout is a weighted adjacency list (Graphs). The frontier is a min-heap (Heaps). Families and the catalog live on the Algorithms Roadmap. It is not a geo-SDK tutorial, not Bellman-Ford, and not a reason to heap-search a graph whose every edge is 1.
The weights are not all 1, the heap is
BFS is enough when every edge is 1, or the graph is unweighted: hop count is the cost, and a FIFO queue already pops vertices in non-decreasing distance. A PriorityQueue on that graph is the same order with extra log V on every offer. This post does not re-teach the queue.
When weights vary, “fewest hops” and “cheapest path” diverge. Dijkstra is BFS with the frontier ordered by current distance, not by discovery time. That swap is legal only while every weight is ≥ 0. A negative edge can make a settled vertex cheaper later; the cousin that is allowed to reopen is Bellman-Ford — one sentence, stop.
Zero is non-negative. Mixed 0/positive weights still want Dijkstra. Uniform positive constants (every edge 5) collapse to hop count; BFS again.
BFS on mixed latencies is not a shortest-path strategy. Neither is Dijkstra on a unit graph you could have queued.
Settle the closest unsettled vertex
Start at a source s. Distances begin at infinity except dist[s] = 0. The heap holds (distance, vertex) pairs. Repeatedly:
- Pop the pair with the smallest distance.
- Skip it if that distance is stale (an older, worse pair for a vertex you already improved).
- Settle the vertex: this
dist[u]will not get cheaper. Non-negative weights are why. - Relax each outgoing edge
u → vof weightw. Ifdist[u] + w < dist[v], write the new distance and push(dist[v], v)— do not hunt the old pair to decrease its key.
Stop when the heap is empty, or when you have settled the destination if you only need one pair. Unreachable vertices stay at infinity.
You do not scan every path. You grow a settled set from s. Each first honest pop is the shortest path to that vertex.
Note: Directed or undirected is the layout’s job. Undirected means both directions already sit in the neighbor lists, with the same non-negative weight unless the domain is asymmetric.
A walked pass, including a stale heap entry
Four vertices. The expensive direct edge into B is the BFS trap: two hops A → B → D cost 11; three hops A → C → B → D cost 3.
directed, non-negative:
A --10--> B --1--> D
| ^
1 1
v |
C --------+
C --100-> D
dist: A=0, B=C=D=∞
pq: (0, A)
pop (0,A) settle A
relax A→B dist[B]=10 push (10,B)
relax A→C dist[C]=1 push (1,C)
pq: (1,C), (10,B)
pop (1,C) settle C
relax C→B dist[B]=2 push (2,B) (10,B) still in the heap
relax C→D dist[D]=101 push (101,D)
pq: (2,B), (10,B), (101,D)
pop (2,B) settle B
relax B→D dist[D]=3 push (3,D)
pq: (3,D), (10,B), (101,D)
pop (3,D) settle D no outgoing
pq: (10,B), (101,D)
pop (10,B) stale (dist[B]=2) skip
pop (101,D) stale (dist[D]=3) skip
distances: A=0, C=1, B=2, D=3
path A→D: A → C → B → D cost 3
not: A → B → D cost 11Each honest pop settles one vertex. The extra (10,B) and (101,D) are ghosts from before a cheaper path showed up. Skipping them is the whole lazy-repush story. Empty graph and a source with no edges: dist[s] = 0, heap drains, everyone else stays unreachable.
Lazy re-push vs decrease-key
Textbooks decrease the key of v in the heap when v gets cheaper. java.util.PriorityQueue has no decrease-key. remove(Object) is a linear scan, then a sift — that is not a logarithmic update.
The Java move is: push a new pair. On pop, if cur.dist != dist[v], the pair is stale; drop it. Heap size can grow to O(E) in the worst case. That is cheaper than implementing a handle map, and it is the procedure this post owns.
A Fibonacci heap is a name in the decrease-key bound (O(E + V log V)). The Heaps post already said not to build one. This sketch will not either.
Note: First honest pop of v is final. You may also keep a settled set and ignore later pairs for that vertex. Same rule, different flag. Do not reopen a settled vertex “just in case” — that is the negative-edge algorithm, not this one.
Java sketch
Weighted list as in the graph post: Edge(to, weight). The heap is a min-heap of current distances. Stale pops are the continue.
record Edge(String to, int weight) {}
record Node(String v, int dist) {}
static Map<String, Integer> dijkstra(
Map<String, List<Edge>> g, String src) {
Map<String, Integer> dist = new HashMap<>();
for (String v : g.keySet()) {
dist.put(v, Integer.MAX_VALUE);
}
dist.put(src, 0);
PriorityQueue<Node> pq = new PriorityQueue<>(
Comparator.comparingInt(Node::dist));
pq.add(new Node(src, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (cur.dist() != dist.getOrDefault(cur.v(), Integer.MAX_VALUE)) {
continue; // stale pair; a better dist[v] already exists
}
for (Edge e : g.getOrDefault(cur.v(), List.of())) {
if (e.weight() < 0) {
throw new IllegalArgumentException("negative weight");
}
long nd = (long) cur.dist() + e.weight();
int best = dist.getOrDefault(e.to(), Integer.MAX_VALUE);
if (nd < best) {
dist.put(e.to(), (int) nd);
pq.add(new Node(e.to(), (int) nd));
}
}
}
return dist;
}Keep a prev map beside dist if you must emit the path: when you write a better dist[v], set prev[v] = u, then walk backward from the destination. Do not store every path prefix on the heap.
Vertices that appear only as Edge.to need a putIfAbsent when you add edges, same as the graph post’s addVertex. The sketch assumes the map already has every vertex key.
Note: Integer.MAX_VALUE + weight wraps to a negative int. The long add is the guard. Unreachable vertices left at MAX_VALUE are a sentinel, not a cost you may add to.
Complexity
Let V be vertices, E edges. Binary heap, lazy re-push, each edge relaxed once from a settled vertex.
| Time | O(E log E) heap ops, usually written O(E log V) |
| Extra RAM | Distances, optional prev, heap of up to O(E) pairs — not a path matrix |
First pop of v | Shortest s ⇝ v (non-negative weights) |
| Fibonacci heap | Name only: O(E + V log V) with decrease-key; do not implement |
Glossary and the Big-O reading live on the hub. The bill that kills the mesh router is the wrong frontier (a queue of hops), not a missing Fibonacci heap.
If you only need s to one t, you may stop when t settles. Worst case you still settle everyone closer than t.
When not to run Dijkstra
Skip it when:
- Every edge is 1 / unweighted. BFS already returns shortest path. A heap of hop-counts is cargo-cult of the name.
- A weight is negative. First-pop-is-final is false. Bellman-Ford is the cousin; this post does not walk it.
- You needed “is
uconnected tov?” That ishasEdge/ a reachability walk, not a distance. - A library already routes. Map SDKs, service-mesh control planes, and graph DBs already run a shortest-path procedure. Pasting this sketch into a request path is the wrong system boundary.
Do not run Dijkstra on an unweighted graph when BFS already answers. Do not reopen settled vertices because a textbook later mentions negative edges.
Also skip it when there is no source: all-pairs on tiny n is a different procedure (Floyd-Warshall). This post is single-source.
JDK: a PriorityQueue, not a Dijkstra class
There is no java.util.Dijkstra. The library piece is the frontier:
- Heap:
PriorityQueuewithComparator.comparingInt(Node::dist) - Layout:
Map<K, List<Edge>>as in the graph post - Optional path: a
prevmap you fill on relax
Prefer BFS when the cost is hop count. Reach for the sketch when weights vary and stay non-negative, or when you are teaching why the first pop is final.
Do not remove from the heap to fake decrease-key. Do not sort the vertex set on every relax. Do not implement a Fibonacci heap.
Cheat sheet
Job: single-source shortest path; every weight ≥ 0
Frontier: min-heap of (dist, vertex) — PriorityQueue
Settle: first honest pop of v is final
Relax: if dist[u]+w < dist[v], write dist[v], push a new pair
Stale: pop with dist != current dist[v] → skip (lazy re-push)
BFS: enough when every edge is 1 / unweighted
Negative: not this algorithm (Bellman-Ford is the cousin)
JDK: PriorityQueue; no decrease-key; no Dijkstra type
Do not: BFS on mixed weights; heap on unit graphs; build a Fibonacci heapDo:
- Order the frontier by current distance, not by discovery time.
- Re-push; skip stale pops. That is the JDK-shaped algorithm.
- Call BFS when hop count is the cost.
Don’t:
- Treat fewest hops as cheapest latency when weights vary.
- Decrease-key with
PriorityQueue.remove. - Reopen a settled vertex, or run this procedure past a negative edge.
- Reach for a Fibonacci heap because a complexity table named one.
Wrap-up
Dijkstra is BFS with a heap instead of a queue, legal while every edge weight is non-negative. Pop the closest unsettled vertex, relax its outgoing edges, lazy-repush when a neighbor gets cheaper, skip ghosts. The first honest pop is the shortest path to that vertex. The JDK gives you PriorityQueue, not decrease-key and not a turnkey router. Use BFS when every edge is 1. Hand-roll the sketch when the weights and the graph are the assignment.
A negative edge is a different cousin: keep relaxing, then one more pass for a cycle.