Dijkstra algorithm explained

Search for "Dijkstra algorithm explained" and you'll find the same recipe everywhere. Pick the node with the smallest distance, update its neighbours, repeat. You can memorise those steps in twenty minutes. But when an interview problem changes the graph structure or adds a constraint you haven't seen, memorised steps fall apart.

The piece most explanations skip isn't the procedure. It's the invariant that makes the procedure correct. Without that, you're following a recipe you can't adapt, can't prove, and can't debug when it gives wrong answers.

What Dijkstra's algorithm actually solves

Dijkstra's algorithm finds the shortest path from a single source node to every other node in a weighted graph with non-negative edge weights. It works by repeatedly selecting the unvisited node with the smallest tentative distance and permanently settling it. This greedy approach is correct because non-negative weights guarantee that no future path through an unsettled node can produce a shorter route.

The problem it solves is single-source shortest path on weighted graphs. Not all-pairs shortest path (Floyd-Warshall's territory) and not shortest path with negative weights (Bellman-Ford). One specific variant, solved efficiently.

If you've studied BFS and DFS, there's a direct connection. BFS finds shortest paths in unweighted graphs because every edge has equal weight. The first time you reach a node through BFS, that's the shortest path. Dijkstra extends this to weighted graphs by replacing the FIFO queue with a priority queue ordered by tentative distance. Instead of processing nodes in discovery order, you process them in order of accumulated weight.

That substitution is the entire algorithm.

If a problem gives you an unweighted graph, BFS is simpler and equally correct. If edges carry different weights, BFS gives wrong answers and Dijkstra is what you need.

Why Dijkstra's algorithm works: The invariant explained

The claim is simple. When you pop a node from the priority queue, its shortest distance is final. No path discovered later will produce a shorter route to that node.

Why? Because every edge weight is non-negative. When node u is popped with tentative distance d(u), every other node still in the queue has a tentative distance >= d(u). Any alternative path to u would need to go through one of those unsettled nodes first, adding at least their distance (already >= d(u)) plus the connecting edges (>= 0). The result can't be smaller than d(u).

That's the greedy settlement invariant. Not complicated, but it's the reason the whole algorithm works. It also immediately reveals the limitation: the proof depends on non-negative edges. Remove that constraint, and the proof collapses.

Why negative weights break everything

Consider three nodes (A, B, C) with edges A→B (weight 1), A→C (weight 3), and C→B (weight -5).

Starting from A, Dijkstra pops B first (distance 1) and settles it. But there's a path A→C→B with total weight 3 + (-5) = -2, which is shorter than 1. Dijkstra never discovers this because B was already settled. The invariant assumed no future path could beat distance 1. With a negative edge, that assumption fails.

This isn't a theoretical edge case. Interview problems sometimes include negative weights specifically to test whether you understand why Dijkstra doesn't work there, not just that it doesn't. The invariant gives you the answer in one sentence. The greedy settlement guarantee requires non-negative edges because a path through an unsettled node with a negative edge can produce a shorter total distance than the already-settled value.

Dijkstra's algorithm explained step by step

Consider a weighted graph with 5 nodes, labeled A through E.

Starting from node A, we want the Dijkstra shortest path to every other node.

Walk through each step.

Notice step 3. B's tentative distance dropped from 4 to 3 because the path A→C→B (total weight 3) is shorter than the direct edge A→B (weight 4). The priority queue naturally surfaces the shorter path first.

That's the invariant in action. By the time B is popped at distance 3, no remaining path can beat it.

Dijkstra time complexity

With a binary heap (Python's heapq), each push and pop takes O(log V). Every edge triggers at most one push, and every node is popped at most once due to the settled check. That gives O((V + E) log V) total, where V is the number of vertices and E is the number of edges.

With a Fibonacci heap, this improves to O(V log V + E), but the constant factors make Fibonacci heaps rarely practical outside textbooks. In interviews, the binary heap version is what you'll implement and what interviewers expect you to analyse.

When to use Dijkstra (and when not to)

The decision framework for shortest path algorithms is smaller than you'd expect. Three questions narrow it down: Are there negative weights? Do you need single-source or all-pairs? Is the graph weighted at all?

One thing that trips people up: some interview problems involve weighted grids where each cell has a traversal penalty, and you need the minimum-weight path from one corner to the other. That's Dijkstra. Engineers who've only practised BFS on unweighted grids sometimes try to force BFS here and get wrong answers. The grid cells carry different weights, so the underlying structure is a weighted graph. Once you recognise that "varying cell weights" maps to "weighted edges," the right algorithm becomes obvious.

Most tutorials don't train that recognition. You learn Dijkstra's steps on an abstract graph but never practise spotting it in disguise. On Codeintuition, the identification lesson for Dijkstra focuses on exactly this. Before you solve any Dijkstra problem, you learn the structural triggers that tell you the pattern applies. The problems that follow (Minimum Cost Path, Cheapest Flights, Teleporter Grid) reinforce those triggers under increasing difficulty.

Common mistakes and how to avoid them

If you want frame-by-frame visual walkthroughs across different graph configurations, the understanding lesson on Codeintuition traces every variable at every step. The graph course covers Dijkstra alongside Bellman-Ford and Floyd-Warshall as part of Codeintuition's learning path ($6.67/month with the annual plan), building the full shortest path decision framework in sequence.

Before reading this, you probably knew the steps. Now you know why each step is correct, where the proof breaks, and which problems are Dijkstra in disguise. Next time you see a problem that doesn't look like a textbook shortest-path graph, check for non-negative weighted edges. If they're there, you already know the algorithm.