What is Dijkstra's Algorithm?

What is Dijkstra's Algorithm? (Simple Explanation)

Definition of Dijkstra’s Algorithm:

Dijkstra’s Algorithm is a shortest path algorithm used to find the minimum distance from a starting node to all other nodes in a graph with non-negative edge weights. It is single source shortest path algorithm. It is commonly used in routing and navigation systems to find the quickest path between locations.

Dijkstra's Algorithm is a way to find the shortest path between one starting point and all other points in a network, like cities connected by roads or computers linked in a network. Imagine you’re trying to find the quickest way to travel from your home to all your friends’ houses. Dijkstra’s algorithm helps you figure that out.

Here’s how it works: You start at the source point (like your home), and from there, you check all the nearby places you can go. You pick the one with the smallest travel time. Then from that place, you look at where else you can go — again choosing the shortest route. The key idea is to always take the smallest step forward, and keep track of the shortest known distance to each location. Step by step, it builds the shortest path to every place on the map until all options are explored.

Steps of Dijkstra's Algorithm:

Begin with the source node.

Assign its distance as 0, and the rest of the nodes' distances as infinity (or a large number). This indicates that we know the distance to the source but not the others yet.

Make all nodes unvisited.

You will progressively mark them visited once their shortest distance is determined.

Select the unvisited node with the smallest known distance.

At the start, this will be the source node.

Verify all its neighboring nodes.

For every neighbor, find the tentative distance from the source node.

If this new route is shorter than the one already recorded, update it.

After verifying all neighbors, tag the current node as visited.

Visited nodes won't be verified again — their shortest path is sealed.

Repeat steps 3–5 until the shortest path to the target node is discovered or all nodes are visited.

Stop the algorithm when the shortest paths to every node have been computed.

Example:

Problem: The graph shown is a weighted and directed graph with non-negative edge weights. The goal is to determine the shortest path from a given source node $S$ to all other nodes using Dijkstra’s Algorithm

Step1: Initialization:

- Set the distance of the source node $S$ to 0.
- Assign all other nodes an initial distance of infinity (∞).
- The predecessor $\pi$ of all vertices is initialized to Nil.
$π (S) = π (s) = Nil$

Step 2. Procedure:

Create a set

Q

that includes all vertices of the graph.
For each vertex

v

, calculate the tentative distance from

S

If the newly found path is shorter than the currently known distance to $v$ , update it:

if

d (v) > d (u) + w (u, v) then update d (v)

Otherwise, keep the existing value.

Vertex (u) s t x y z

d(u) 0 ∞ ∞ ∞ ∞

π(u) Nil Nil Nil Nil Nil

Now, remove node

S

from

Q

and proceed to relax the edges.

Updated Table – After Relaxing Neighbors of s

Vertex (u) t x y z

d(u) 10 ∞ 5 ∞

π(u) s Nil s Nil

Edge Relaxation Logic:

Let’s relax edge $(s, t)$ where:

So, update: d(t)=10

d(t)>d(s)+w(s,t)⇒∞>0+10⇒∞>10

d(t) = 10

Similarly, for $(s, y)$ :

d(y)>d(s)+w(s,y)⇒∞>0+5⇒∞>5

Thus:

d(y) = 5

Step 3:

From 2 nodes(t,y) the minimum distance is d(sy)=5. now extract y from set Q.

so, extract from Q[Q=(t, x, ~~y, z~~)] and relax the edges

adjacent to y are vertices t, x, y so, let us compute d(y, t),d(y, z),d(y, z) from source S

🔄 Edge Relaxation from Vertex `y`

Vertex y is connected to three neighboring vertices: t, x, and z. The algorithm now checks whether taking a path through y provides a shorter route to these neighbors. This is done using the relaxation technique, where we compare the current known distance with a new potential distance via y.

✅ For Vertex `t`:

d[t] = \min(10, 5 + 3) = 8 \quad \Rightarrow \quad \text{Updated!}

as 10 greater than 8

d(t)=8

Now t is reachable with a shorter distance through y.

✅ For Vertex `x`:

d[x] = \min(∞, 5 + 9) = 14 \quad \Rightarrow \quad \text{Updated!}

as ∞ greater than 14

d(v)=14

This gives the first known shortest path to x.

✅ For Vertex `z`:

d[z] = \min(∞, 5 + 2) = 7 \quad \Rightarrow \quad \text{Updated!}

as ∞ greater than 7

d(z)=7