Introduction

Dijkstra's algorithm answers one very specific question: given a starting node in a graph with non-negative edge weights, what is the shortest known distance to every other reachable node? The algorithm is often taught as a simple recipe, but the important part is why it works. Once the smallest tentative distance is removed from the priority queue, that distance is final, and the algorithm never needs to improve it again.

When Dijkstra Applies

Dijkstra is the right tool when all edge weights are non-negative. That condition is not a minor detail. It is the reason the greedy step is valid.

Use Dijkstra when:

• edges have weights 0 or larger
• you want shortest paths from one source
• the graph may be directed or undirected

Do not use plain Dijkstra when:

• any edge weight is negative
• you need all-pairs shortest paths and will run the source query many times
• the graph state changes after every query and precomputation is more appropriate

If negative edges exist, use Bellman-Ford or another algorithm designed for that model.

The Core Greedy Invariant

Dijkstra keeps a best-known distance for each node. At each step it chooses the unprocessed node with the smallest tentative distance.

Why is that safe?

Because with non-negative edges, any alternative path reaching that node later would already be at least as expensive. No unseen path can come from "below" and suddenly beat the distance you just extracted from the min-heap.

That is the entire idea behind the algorithm's correctness.

A Standard Priority-Queue Implementation

Here is a complete Python version using an adjacency list and heapq:

1import heapq
2
3
4def dijkstra(graph, source):
5    dist = {node: float("inf") for node in graph}
6    prev = {node: None for node in graph}
7    dist[source] = 0
8
9    pq = [(0, source)]
10
11    while pq:
12        current_dist, node = heapq.heappop(pq)
13        if current_dist != dist[node]:
14            continue
15
16        for neighbor, weight in graph[node]:
17            new_dist = current_dist + weight
18            if new_dist < dist[neighbor]:
19                dist[neighbor] = new_dist
20                prev[neighbor] = node
21                heapq.heappush(pq, (new_dist, neighbor))
22
23    return dist, prev
24
25
26def reconstruct_path(prev, target):
27    path = []
28    while target is not None:
29        path.append(target)
30        target = prev[target]
31    return list(reversed(path))
32
33
34graph = {
35    "A": [("B", 1), ("C", 4)],
36    "B": [("C", 2), ("D", 5)],
37    "C": [("D", 1)],
38    "D": [],
39}
40
41dist, prev = dijkstra(graph, "A")
42print(dist)
43print(reconstruct_path(prev, "D"))

This prints the shortest distances from A and reconstructs one shortest path to D.

Why the Heap May Contain Stale Entries

A common implementation detail confuses beginners: the same node can appear in the priority queue more than once.

That is okay.

When a better path is discovered, the algorithm pushes a new pair into the heap. Later, if an old pair is popped, the line:

if current_dist != dist[node]:
    continue

skips it as stale.

This is often simpler than trying to implement a decrease-key operation manually.

Time Complexity

With an adjacency list and a binary heap, the typical complexity is:

• 'O((V + E) log V)'

where:

• 'V is the number of vertices'
• 'E is the number of edges'

That is efficient for sparse graphs and is one reason Dijkstra is so widely used.

For dense graphs, other representations or algorithms may be more appropriate, but the heap-based version is the normal practical baseline.

Typical Variations

Many questions about Dijkstra are really questions about its variants.

Examples:

• stop early when the target node is extracted from the heap if you need only one destination
• add predecessor tracking if you need the actual path, not just the distances
• combine with a heuristic to get A-star when you know something about the remaining distance

These are extensions of the same shortest-path foundation, not separate ideas.

Common Pitfalls

The biggest mistake is using Dijkstra on graphs with negative edges. The algorithm may still run, but the results are no longer guaranteed to be correct.

Another mistake is marking a node visited too early, such as when it is first inserted into the heap. A node becomes final only when the current smallest distance is popped from the heap.

Developers also often forget to reconstruct the path. Distance tables alone do not show which route actually achieved the minimum.

Finally, be careful with disconnected graphs. Unreachable nodes should keep distance infinity; that is not a bug.

Summary

• Dijkstra solves single-source shortest paths on graphs with non-negative weights.
• Its greedy step works because non-negative edges preserve the smallest extracted distance.
• A heap-based implementation is the standard practical approach.
• Stale heap entries are normal and can be skipped safely.
• If the graph has negative edges, use a different algorithm.