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. If you only care about one destination, you can stop as soon as that destination is settled.

The core move is greedy: always continue from the unsettled node with the smallest known distance. That works only under the nonnegative-weight condition.

What Dijkstra's Algorithm Solves

Use Dijkstra's algorithm when you have a graph with costs on edges and you want the cheapest route. The cost might represent distance, travel time, energy, or some other quantity you want to minimize.

It works on directed or undirected graphs. The key condition is explicit: every edge weight must be at least $0$.

How The Algorithm Works

Each node keeps a tentative distance from the start node. At the beginning, the start node has distance $0$ and every other node has distance $\infty$.

Then repeat this loop:

1. Pick the unsettled node with the smallest tentative distance.
2. Check each neighbor through that node.
3. If the new route is cheaper, update the neighbor's distance.
4. Mark the current node as settled.

Step 3 is called relaxation. A settled node is finished: its shortest distance is final, provided the graph has no negative edge weights.

Dijkstra's Algorithm Step By Step

Here is the full procedure in compact form:

1. Choose a start node.
2. Set its distance to $0$ and every other distance to $\infty$.
3. Select the unsettled node with the smallest tentative distance.
4. Relax its outgoing edges.
5. Mark that node as settled.
6. Repeat until all reachable nodes are settled, or stop once your target node is settled.

If you also store which previous node caused each update, you can recover the actual path, not just the final distance.

Worked Shortest-Path Example

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:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Settle $A$ first and relax its edges:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

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:

$$3+1=4$$

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:

$$A \to C \to B \to D$$

with total cost:

$$1+2+1=4$$

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 Nonnegative Weights Matter

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.

Common Mistakes With Dijkstra's Algorithm

Using it with a negative edge

Even one negative edge can break the greedy logic. If negative weights are possible, use a different shortest-path method.

Treating "seen" as "finished"

A node can already have a tentative distance and still be unfinished. Only a settled node has a final shortest distance.

Forgetting the previous-node table

Distances tell you the cost. If you also want the route itself, store 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.

Try A Similar Problem

Draw a graph with five nodes and positive edge weights, then run Dijkstra's algorithm by hand with a distance table. If you want a good next step, try your own version on a new graph and check exactly when each node becomes safe to settle.