Dijkstra's Algorithm — Shortest Path Step by Step

Dijkstra's algorithm finds shortest paths from one start node in a weighted graph, as long as every edge weight is nonnegative. Reach for it whenever you can model a problem as moving through a graph with nonnegative costs and you want the cheapest route. If you only care about one destination, you can stop as soon as that destination is settled.

The cost might represent distance, travel time, energy, or anything else you want to minimize, and the algorithm works on directed or undirected graphs. The one condition you cannot skip: every edge weight must be at least $0$. The core move is greedy, always continuing from the unsettled node with the smallest known distance, and that move is only safe under the nonnegative-weight condition.

The Procedure, Step By Step

1. Set the starting distances. Give the start node distance $0$ and every other node an initial distance of infinity.
2. Pick the smallest tentative distance. Among the unvisited nodes, choose the one with the smallest current distance.
3. Relax its edges. Update each neighbor if going through the chosen node gives a shorter path.
4. Settle the node. Mark the chosen node as settled and repeat until the destination or all reachable nodes are done.

In compact form, the full loop is: choose a start node; set its distance to $0$ and every other distance to $\infty$; select the unsettled node with the smallest tentative distance; relax its outgoing edges; mark that node as settled; repeat until all reachable nodes are settled, or stop once your target node is settled.

Step 3 is called relaxation. A settled node is finished: its shortest distance is final, provided the graph has no negative edge weights. If you also store which previous node caused each update, you can recover the actual path, not just the final distance.

Running The Procedure On A Full Graph

Suppose the graph has these edge weights:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

We want the shortest path from $A$ to $D$. Start with:

Settle $A$ first and relax its edges:

The smallest unsettled distance is now at $C$, so settle $C$ next. Going through $C$:

• Through $C$, the path to $B$ costs $1+2=3$, which improves on $4$, so update $\text{dist}(B)=3$.
• Through $C$, the path to $D$ costs $1+5=6$, so set $\text{dist}(D)=6$.

Now $B$ has the smallest unsettled distance, so settle $B$. Going through $B$, the path to $D$ costs:

That improves on $6$, so update $\text{dist}(D)$ from $6$ to $4$. Now $D$ is the smallest unsettled node. Settle it, and stop.

The shortest path is:

with total cost:

This example shows the key pattern: a route that first looked worse, $A \to B$, became better later through $C$. Dijkstra's algorithm allows that while $B$ is still unsettled. Once a node is settled, its distance will not change.

Why The Greedy Step Is Safe

The greedy choice in step 2 deserves a justification, because it is exactly what breaks without the nonnegative condition.

Suppose the current cheapest unsettled node has distance $d$. Any new path to that node found later would have to come from another unsettled node whose tentative distance is at least $d$, and then add an edge of weight at least $0$. So that later route cannot beat $d$. That is why settling the smallest tentative distance is safe when all weights are nonnegative.

If a negative edge exists, that argument breaks. A path that looks expensive now might become cheaper later, which means settling a node too early can give the wrong answer.

Where Students Slip, And How To Check Each Step

Using it with a negative edge

Even one negative edge can break the greedy logic. Self-check: scan every weight for a negative value before you start; if one exists, switch to a different shortest-path method.

Treating "seen" as "finished"

A node can already have a tentative distance and still be unfinished. Self-check: only a settled node has a final shortest distance, so do not lock in a value until you settle it in step 4.

Forgetting the previous-node table

Distances tell you the cost but not the route. Self-check: if you need the path, confirm you stored which node last improved each distance.

Where Dijkstra's Algorithm Is Used

Dijkstra's algorithm is used when a problem can be modeled as moving through a graph with nonnegative costs:

• Route planning on maps
• Network routing
• Robot motion on weighted grids
• Game pathfinding when movement costs vary

It is also a standard example of a greedy algorithm whose correctness depends on a precise condition. To internalize the procedure, draw a graph with five nodes and positive edge weights, run the algorithm by hand with a distance table, and watch exactly when each node becomes safe to settle.