Dijkstra’s Algorithm Explained

Dijkstra’s algorithm is used to find the minimum cost path from a single source node to all other nodes in a graph with non-negative edge weights.

Unlike Floyd–Warshall (all pairs), Dijkstra focuses on one starting point.

For Example

Each letter (a–z) is a node
Each allowed transformation is a directed edge
Each edge has a cost
We want the cheapest cost from a source letter to all others

1. Think of Letters as Cities

Imagine each letter is a city and each transformation is a one-way road with a toll.

a → b (2)
a → c (4)
b → c (1)
c → d (3)

You start in city a and want to find the cheapest way to reach every other city.

2. Distance Array

We maintain an array:

dist[x] = minimum cost to reach x from the source

Initial setup:

dist[source] = 0
All other distances = infinity (∞)
No node has been visited yet

Example (source = a):

a: 0
b: ∞
c: ∞
d: ∞

3. The Core Idea

Always expand the currently cheapest unvisited node.

Pick the unvisited node with the smallest known distance
Try to improve distances to its neighbors
Mark the node as visited (finalized)

Once a node is visited, its shortest distance is guaranteed.

4. Relaxation Step

When we move from node u to neighbor v:

if dist[u] + cost(u → v) < dist[v]:
    dist[v] = dist[u] + cost(u → v)

This process is called relaxation.

5. Step-by-Step Example

Graph:

a → b (2)
a → c (4)
b → c (1)
c → d (3)

Step 1: Start at a

dist[a] = 0
dist[b] = 2
dist[c] = 4
dist[d] = ∞

Mark a as visited.

Step 2: Visit b

Check b → c:

2 + 1 = 3 < 4

Update:

dist[c] = 3

Mark b as visited.

Step 3: Visit c

Check c → d:

3 + 3 = 6

Update:

dist[d] = 6

6. Final Distances

a → a = 0
a → b = 2
a → c = 3
a → d = 6

7. Why It Always Works

Edge costs are non-negative
The smallest unvisited distance is always optimal
Once a node is finalized, no cheaper path can appear later

This greedy choice is provably correct.

8. Pseudocode

initialize dist[] with infinity
dist[source] = 0
priority queue pq
pq.push(source, 0)

while pq not empty:
    u = node with smallest dist
    if u is visited:
        continue
    mark u as visited

    for each neighbor v of u:
        if dist[u] + cost(u → v) < dist[v]:
            dist[v] = dist[u] + cost(u → v)
            pq.push(v, dist[v])

9. When to Use Dijkstra

Use Dijkstra when:

You need shortest paths from one source
All edge weights are non-negative

Do NOT use when:

Negative edge weights exist (use Bellman–Ford)
You need all-pairs shortest paths (use Floyd–Warshall)

Search This Blog