The invariant that makes the greedy pop legal
Dijkstra's algorithm keeps a tentative distance for every node, initialises the source to zero and everything else to infinity, and then repeatedly takes the unsettled node with the smallest tentative distance, declares that distance final, and relaxes its outgoing edges.
The step that needs justifying is "declares that distance final". Suppose you pop node u with tentative distance d, and suppose some cheaper route to u exists. That route must leave the settled set at some point, reaching an unsettled node v before continuing to u. But v's tentative distance is already at most the cost of the route as far as v, and you popped u rather than v, so u's distance is no greater than v's. The rest of the route from v to u then has to have total weight less than zero for the whole thing to beat d. If every weight is non-negative, that is impossible, and d is final.
Being able to give that argument, rather than describing the mechanics of the loop, is the main thing this question tests. It also tells you exactly where the algorithm will fail, because the argument used the non-negativity assumption in precisely one place.
Stale entries, and the decrease-key you do not have
The textbook presentation assumes a priority queue supporting decrease-key, so when a relaxation improves a node's tentative distance the existing entry is updated in place. Standard library heaps do not offer that. Java's PriorityQueue has no decrease-key, and removing an arbitrary element from it is a linear scan.
The practical answer is lazy deletion: push a new entry every time you improve a distance, accept that the heap now holds obsolete entries for nodes you have already improved or settled, and discard them on the way out. The guard is one comparison at the top of the loop.
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);
dist[source] = 0;
int[] prev = new int[n];
Arrays.fill(prev, -1);
PriorityQueue<long[]> heap = new PriorityQueue<>(Comparator.comparingLong(e -> e[0]));
heap.add(new long[] { 0, source });
while (!heap.isEmpty()) {
long[] top = heap.poll();
int u = (int) top[1];
if (top[0] > dist[u]) continue;
for (Edge e : adjacency[u]) {
long candidate = dist[u] + e.weight;
if (candidate < dist[e.to]) {
dist[e.to] = candidate;
prev[e.to] = u;
heap.add(new long[] { candidate, e.to });
}
}
}
Two details in that code are worth defending out loud. The distances are 64-bit because a long path over 32-bit weights can exceed the 32-bit range, and the reason the sentinel never participates in an addition is that a node is only ever pushed after its distance has become finite. The predecessor array is filled during relaxation rather than reconstructed at the end, because distances alone do not determine which of several equally cheap predecessors you came from.
One negative edge, on three nodes
Now the second half of the question, and it deserves a worked graph rather than a generalisation.
Take nodes A, B and C. A to B costs 2. A to C costs 5. C to B costs minus 4. There is no negative cycle here at all: every edge points forward and nothing returns.
Run the algorithm from A. Relaxing A gives B a tentative 2 and C a tentative 5. The smallest unsettled distance is B at 2, so B is popped and settled at 2. Then C is popped at 5, and relaxing C to B offers 5 plus minus 4, which is 1. But B is settled, and the stale check means the improvement is either ignored or, worse, applied after B's value has already been reported. The correct answer for B is 1 by way of C, and the algorithm returns 2.
This is the point most candidates get half right. They know Dijkstra "requires non-negative weights" and they explain the requirement by talking about negative cycles, which is the wrong explanation: a negative cycle makes the shortest path undefined for every algorithm, whereas a single negative edge on an acyclic graph leaves every shortest path perfectly well defined and still breaks Dijkstra. The failure is in the settling rule, not in the existence of an answer.
The fix is not a patch. Allowing settled nodes back into the queue turns the running time exponential in the worst case. Bellman-Ford is the correct replacement: relax every edge V minus 1 times, at O of V times E, and one extra pass that still improves something proves a negative cycle is reachable. For all-pairs distances with some negative weights, Johnson's algorithm reweights the graph using Bellman-Ford potentials so that Dijkstra becomes valid again, which is the answer that shows you understand the constraint rather than merely obeying it.
Cost, and the cases where a heap is overkill
With a binary heap and lazy deletion the bound is O of open bracket V plus E close bracket log V, since each edge can push at most one entry and each pop costs a logarithm. With a Fibonacci heap the theoretical bound improves to O of E plus V log V, and in practice the constants rarely justify it.
Two special cases are worth volunteering. If every edge has the same weight, a plain breadth-first search gives the same answer in O of V plus E with no heap at all, and reaching for Dijkstra there is a small mark against you. If weights are only 0 or 1, a deque used as a two-ended queue, pushing zero-weight relaxations to the front, achieves the same linear bound. Recognising when the priority queue is unnecessary is the same skill as recognising when it is mandatory.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).