Dijkstra Calculator

Pseudocode

Dijkstra is a greedy algorithm whose entire correctness rests on one claim: the closest unsettled node can never be improved later. A priority queue supplies that node in O(log V).

Dijkstra(graph, source):
    for each vertex v: dist[v] = infinity
    dist[source] = 0
    pq = priority queue containing (0, source)

    while pq is not empty:
        (d, u) = pq.extractMin()
        if d > dist[u]: continue      // stale entry, skip
        for each edge (u, v, w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                pq.insert((dist[v], v))

The stale-entry check matters. Rather than decreasing a key inside the heap, which most standard libraries do not support, the usual implementation pushes a duplicate entry and ignores any entry whose recorded distance no longer matches. This is called lazy deletion, and it is why the queue can hold up to E entries rather than V.

Worked example, step by step

Run Dijkstra from A on a weighted graph where the greedy choice pays off, watching the settled set grow.

Example graph: Undirected edges A-B (4), A-C (2), C-B (1), B-D (5), C-D (8).

1. Initialise. dist = A 0, B infinity, C infinity, D infinity. Queue holds (0, A).
2. Settle A at 0. Relax A-B giving dist[B] = 4, and A-C giving dist[C] = 2. Queue holds (2, C) and (4, B).
3. Settle C at 2. C is closer than B, so it comes out first. Relax C-B: 2 + 1 = 3, better than the recorded 4, so dist[B] = 3 and a new entry (3, B) is pushed. Relax C-D: 2 + 8 = 10, so dist[D] = 10.
4. Settle B at 3. The (3, B) entry surfaces before the stale (4, B). Relax B-D: 3 + 5 = 8, better than 10, so dist[D] = 8.
5. Skip the stale entry. The old (4, B) entry now surfaces. Since 4 is greater than dist[B] of 3, it is discarded without reprocessing B. This is the lazy deletion in action.
6. Settle D at 8. Nothing left to improve. The algorithm terminates.

Final distances are A 0, C 2, B 3, D 8, with the shortest path to D running A to C to B to D. Note that the direct A-B edge of weight 4 is never used: routing through C costs 3. Note also that nodes settle in distance order 0, 2, 3, 8, which is the property the greedy argument depends on.

Complexity, and where it comes from

Time: O((V + E) log V) · Space: O(V)

With a binary heap, each of the V vertices is extracted once at O(log V), and each of the E edges can trigger one insertion at O(log V), giving O((V + E) log V). With lazy deletion the heap holds up to E entries, so extraction is O(log E), but since E is at most V squared, log E is at most 2 log V and the bound is unchanged. A Fibonacci heap improves the theoretical bound to O(E + V log V) because decrease-key becomes O(1) amortised, though the constants are bad enough that binary heaps usually win in practice. On a dense graph, a simple array scan for the minimum gives O(V squared), which beats the heap when E approaches V squared.

When to use Dijkstra's Algorithm, and when not to

Dijkstra is the default for weighted shortest paths. What replaces it depends on which of its assumptions your graph breaks.

Common pitfalls

• Using it with negative edge weights. This is the classic misuse. Dijkstra settles a node permanently when it leaves the queue; a negative edge found later would have improved it, but it is never reconsidered. The result is silently wrong, not an error, which makes the bug hard to spot. Use Bellman-Ford instead.
• Forgetting the stale-entry check. Without the `if d > dist[u]: continue` guard, a vertex is reprocessed once per queue entry. It still terminates and still gives correct answers, but it re-relaxes edges needlessly and can degrade badly on graphs with many improvements.
• Stopping at the first sight of the target. Reaching the target during relaxation does not mean its distance is final. It is final only when the target is extracted from the queue. Breaking early on discovery gives wrong answers; breaking on extraction is correct and is a genuine optimisation.
• Treating zero-weight edges as a problem. Zero weights are fine. Only strictly negative weights break the argument, because the greedy proof needs distances to be nondecreasing along a path, and zero preserves that.
• Rebuilding the whole graph for each query. One Dijkstra run gives distances from the source to every node, not just one. If you need many sources, that is a different problem: consider Floyd-Warshall or Johnson rather than running Dijkstra V times without thinking.

Frequently asked questions

What is Dijkstra's algorithm used for?

It finds the shortest path from one source to all other nodes in a graph with nonnegative edge weights. It drives GPS and transit routing, internet routing protocols such as OSPF and IS-IS, network latency analysis, and game pathfinding when no heuristic is available.

What is the time complexity of Dijkstra's algorithm?

O((V + E) log V) with a binary heap, which is the standard implementation. A Fibonacci heap lowers it to O(E + V log V) in theory, though constants usually make binary heaps faster in practice. On dense graphs a plain array scan gives O(V squared), which can beat the heap when E approaches V squared.

Why does Dijkstra's algorithm fail with negative weights?

Because it settles each node permanently the moment that node has the smallest tentative distance in the queue, on the assumption that no later path can be shorter. A negative edge violates that assumption: a path discovered afterwards can reduce an already settled distance. Dijkstra never revisits settled nodes, so it returns a wrong answer without any error.

What is the difference between Dijkstra and A*?

A* is Dijkstra plus a heuristic estimate of the remaining distance to a specific target. Dijkstra expands nodes in order of distance from the source and finds paths to everything; A* expands in order of estimated total path cost and heads toward one target, exploring far fewer nodes. With a zero heuristic, A* is exactly Dijkstra.

Does Dijkstra's algorithm work on undirected graphs?

Yes. An undirected edge is simply two directed edges of equal weight, so the algorithm applies unchanged. The only real requirement is that no weight is negative.