Dijkstra's Algorithm

Dijkstra's algorithm is one of the most important algorithms for solving the single-source shortest-path problem in a weighted graph.

1. What Problem Does Dijkstra's Algorithm Solve?

Suppose we have a directed, weighted graph

G = (V, E)

and a source vertex s.

We want to find the shortest distance from s to every other vertex.

For example:


        4
   A -------- B
   |          |
  2|          |3
   |          |
   C -------- D
        1

If A is the source, we want to determine:


A → A
A → B
A → C
A → D

and find the minimum total weight for each path.

2. Important Restriction

Dijkstra's algorithm requires:

w(u,v)≥0

for every edge (u,v).

In other words:

Dijkstra's algorithm does not work correctly when the graph contains negative-weight edges.

This is one of the most important conditions students should remember.

3. Connection with BFS

Dijkstra's algorithm can be viewed as a generalization of Breadth-First Search to weighted graphs.

In BFS, every edge effectively has weight:

Therefore, BFS can use a simple FIFO queue.

For a weighted graph, however, different edges can have different weights:


A --2-- B

A --10-- C

A --5-- D

So we cannot simply process vertices in the order in which they were discovered.

We need to process the vertex with the smallest current shortest-path estimate.

Therefore:


BFS
   ↓
FIFO Queue

Dijkstra
   ↓
Min-Priority Queue

4. The Wave Analogy

A useful wave analogy.

Imagine that a wave starts from the source s.

In an unweighted graph:


       distance 1
          ↓
       distance 2
          ↓
       distance 3

Every edge takes the same amount of time to cross.

But in a weighted graph:


A --2-- B

A --10-- C

A --5-- D

the wave takes:

2 units to reach B,
10 units to reach C,
5 units to reach D.

Therefore, Dijkstra always chooses the vertex where the wave has arrived earliest.

That is why it repeatedly chooses the vertex having the smallest shortest-path estimate.

5. The Main Idea of Dijkstra

Dijkstra maintains a set:

where:

S contains vertices whose final shortest-path distances from the source have already been determined.

Initially:


S = ∅

At every iteration:

Choose the vertex u outside S having the smallest d[u].
Add u to S.
Relax all edges leaving u.

The process continues until every vertex belongs to S.

6. What is `d[v]`?

Dijkstra maintains an attribute:

v.d

called the shortest-path estimate.

Initially:


s.d = 0

and for every other vertex:


v.d = ∞

So initially:


       s      A      B      C
       0      ∞      ∞      ∞

As the algorithm discovers better paths, these values decrease.

7. What is Relaxation?

Relaxation is the fundamental operation used by Dijkstra.

Suppose we have an edge:


u ----w(u,v)----> v

and currently:


u.d
v.d

are known.

We ask:

Can I obtain a shorter path to v by going through u?

The possible new distance is:

u . d + w (u, v)

If:

u . d + w (u, v) < v . d

then we update:

v . d = u . d + w (u, v)

and:

v . π = u

where v.π stores the predecessor of v.

In simple terms:


If going through u is cheaper:

        update v.d
        update v.π

8. Example of Relaxation

Suppose:


A ----4----> B

and:


A.d = 6
B.d = 10

Going through A gives:

A . d + w (A, B) = 6 + 4 = 10

Since:

10 <= 10

there is no improvement.

Now suppose:


B.d = 15

Then:

6 + 4 = 10 < 15

Therefore we update:


B.d = 10
B.π = A

This operation is called relaxation.

9. Dijkstra's Algorithm — Pseudocode


DIJKSTRA(G, w, s)

1. INITIALIZE-SINGLE-SOURCE(G, s)
2. S = ∅
3. Q = ∅
4. for each vertex u ∈ G.V
5.     INSERT(Q, u)

6. while Q ≠ ∅
7.     u = EXTRACT-MIN(Q)
8.     S = S ∪ {u}

9.     for each vertex v ∈ Adj[u]
10.        RELAX(u, v, w)

11.        if the call of RELAX decreased v.d
12.            DECREASE-KEY(Q, v, v.d)

This is the formulation using a min-priority queue.

10. Understanding the Algorithm Step by Step

Step 1: Initialize

Set:


s.d = 0

and for every other vertex:


v.d = ∞

Also:


v.π = NIL

Initially:


S = ∅

Step 2: Put All Vertices in the Priority Queue

All vertices are inserted into the min-priority queue.

The priority is determined by:

v.d

Initially:


s.d = 0

and all others are infinity.

Therefore, the source s will be extracted first.

11. Step 3: Extract the Minimum

The algorithm performs:


u = EXTRACT-MIN(Q)

This selects the vertex outside S having the smallest d value.

Then:


S = S ∪ {u}

The important point is:

Once a vertex is removed from Q and added to S, its shortest-path distance is final.

This is where Dijkstra differs from algorithms that may repeatedly revise vertices.

12. Step 4: Relax the Edges

After selecting u, Dijkstra examines every edge leaving u.

For each:


(u,v)

it performs:


RELAX(u,v,w)

If the relaxation improves v.d, the priority queue is updated using:


DECREASE-KEY

13. Complete Example

Consider the following graph:


             10
        ┌──────────► B
        │            │
        │            │ 1
        │            
        A ──2──────► C
        │            │
        │            │ 3
        │            ▼
        └──5───────► D

Edges:

Edge	Weight
A → B	10
A → C	2
A → D	5
C → B	1
C → D	3

Let:


Source = A

14. Initial State

Initially:


A.d = 0

B.d = ∞
C.d = ∞
D.d = ∞

And:


S = ∅

15. First Iteration

The minimum d value is:


A.d = 0

So:


u = A

Add A to S:


S = {A}

Now relax A's outgoing edges.

Edge A → B

0 + 10 = 10

Therefore:


B.d = 10
B.π = A

Edge A → C

0 + 2 = 2

Therefore:


C.d = 2
C.π = A

Edge A → D

0 + 5 = 5

Therefore:


D.d = 5
D.π = A

Current state:


A = 0
B = 10
C = 2
D = 5

16. Second Iteration

Among vertices outside S:


B = 10
C = 2
D = 5

The smallest is:


C = 2

Therefore:


u = C

Add C:


S = {A,C}

Now relax C's outgoing edges.

Edge C → B

Current:


B.d = 10

Going through C gives:

C . d + w (C, B)

= 2 + 1 = 3

Since:

3 < 10

we update:


B.d = 3
B.π = C

Edge C → D

Current:


D.d = 5

Going through C gives:

2 + 3 = 5

Since:

5= < 5

there is no improvement.

So:


D.d = 5

remains unchanged.

Current state:


A = 0
C = 2
B = 3
D = 5

17. Third Iteration

The vertices outside S are:


B = 3
D = 5

The smallest is:


B = 3

Add B:


S = {A,C,B}

Process B's outgoing edges.

There is no improvement to any remaining vertex.

18. Fourth Iteration

The only remaining vertex is:


D = 5

Add D:


S = {A,C,B,D}

Now:


Q = ∅

The algorithm terminates.

19. Final Shortest-Path Distances

We obtain:

Vertex	Shortest distance from A	Predecessor
A	0	NIL
C	2	A
B	3	C
D	5	A

Therefore:

Shortest path A → C


A → C

Cost:

Shortest path A → B


A → C → B

Cost:

2 + 1 = 3

rather than the direct edge:


A → B = 10

Shortest path A → D


A → D

Cost:

20. The Shortest-Path Tree

The predecessor values are:


C.π = A
B.π = C
D.π = A

Therefore, the shortest-path tree is:

After Dijkstra's algorithm terminates, the predecessor subgraph forms a shortest-paths tree rooted at the source.

21. Why Does Dijkstra Work?

The key reason is the nonnegative edge-weight condition.

Suppose Dijkstra selects vertex u because it has the smallest current distance among all vertices not yet in S.

Could there be a shorter path to u that we haven't discovered yet?

If there were, that path would have to pass through some vertex outside S.

But because all edge weights are nonnegative, moving farther along that path cannot suddenly produce a smaller distance than the vertex already selected.

Therefore, when Dijkstra extracts the minimum:


u = EXTRACT-MIN(Q)

we can safely conclude:

u . d = δ (s, u)

where:

δ(s,u)

is the true shortest-path distance from s to u.

22. Why Negative Edges Cause a Problem

Suppose:


A ----2----> B

and:


A ----5----> C ----(-10)----> B

Initially Dijkstra might think:


B = 2
C = 5

and select B first because:


2 < 5

But the path:


A → C → B

has cost:

5 + (- 10) = - 5

which is shorter than 2.

So the assumption that the smallest current distance is final breaks down.

Hence:

Dijkstra requires nonnegative edge weights.

23. Complexity Analysis

This is particularly important because the complexity of Dijkstra depends on the implementation of the min-priority queue.

We analyzes three major priority-queue operations:

INSERT
EXTRACT-MIN
DECREASE-KEY

24. How Many Times Are These Operations Performed?

This is the key to understanding the complexity.

INSERT

Every vertex is inserted exactly once.

Therefore:

V INSERT operations

EXTRACT-MIN

Every vertex is removed from the priority queue exactly once.

Therefore:

V EXTRACT-MIN operations

DECREASE-KEY

Every edge is examined exactly once when its source vertex is processed.

There are E edges.

A relaxation may cause a DECREASE-KEY.

Therefore, there can be at most E DECREASE-KEY operations.

Thus:

At most E DECREASE-KEY operations

This is an example of aggregate analysis: rather than analyzing each iteration separately, we count the total number of operations over the entire algorithm.

25. Complexity with a Simple Array

The simplest implementation stores the d values in an array.

For example:


vertex:   A    B    C    D
d:        0    3    2    5

INSERT

Each insertion takes:

O(1)

There are V insertions:

O(V)

DECREASE-KEY

Updating a value in an array takes:

O(1)

There are at most E such operations:

O(E)

EXTRACT-MIN

This is the expensive operation.

To find the minimum d value, we may need to scan all V vertices.

Therefore:

O(V)

per EXTRACT-MIN.

There are V extractions:

O(V^2)

Total

Therefore:

O (V) + O (V^^{2}) + O (E)

which gives:

O(V^2+E)

Since a directed graph can have:

E \leq V^^{2}

we can write:

O(V^2)

This is the straightforward implementation .

26. Complexity with a Binary Min-Heap

Now consider a binary min-heap.

This is the implementation normally emphasized when teaching the efficient version of Dijkstra.

BUILD HEAP

The heap can be built in:

O(V)

EXTRACT-MIN

Each operation takes:

O(logV)

There are V such operations.

Therefore:

O(VlogV)

DECREASE-KEY

Each DECREASE-KEY takes:

O(logV)

There are at most E such operations.

Therefore:

O(ElogV)

INSERT

The initial construction can be handled in:

O(V)

using a heap construction approach.

27. Total Binary-Heap Complexity

Putting everything together:

O (V) + O (V log V) + O (E log V)

Therefore:

O((V+E)logV)

For a typical connected graph where:

E = Ω (V)

we can simplify this to:

O(ElogV)

This is the complexity statedfor the binary-heap implementation in the usual sparse-graph setting.

28. Comparing the Two Implementations

Implementation	INSERT	EXTRACT-MIN	DECREASE-KEY	Total
Array	O(1)	O(V)	O(1)	O(V²)
Binary min-heap	O(log V)*	O(log V)	O(log V)	O((V+E) log V)
Fibonacci heap	O(1) amortized	O(log V) amortized	O(1) amortized	O(E + V log V)

* the initial queue can be built directly as a heap.

29. When Is the Binary Heap Better?

Compare:

Array

O(V^2)

Binary heap

O(ElogV)

If the graph is sparse, then:

E ≪ V^^{2}

and the binary heap is significantly better.

CLRS states the improvement in particular when:

E = o (\frac{V^ ^{2}}{log V/})

30. Dijkstra vs BFS vs Prim

Since you have just covered BFS and Prim, this comparison is very useful for students.

Feature	BFS	Dijkstra	Prim
Problem	Shortest paths	Shortest paths	MST
Graph	Unweighted	Weighted	Weighted
Negative edges	Not applicable	❌ Not allowed	Edge weights normally considered for MST
Main structure	Queue	Min-priority queue	Min-priority queue
Selection	FIFO	Smallest `d[v]`	Smallest `key[v]`
What does key mean?	Distance in levels	Shortest-path estimate	Cheapest connection to tree
Output	BFS tree	Shortest-path tree	MST
Greedy?	—	Yes	Yes

The important distinction between Dijkstra and Prim is:

Dijkstra

Asks:

What is the shortest path from the source to this vertex?

Prim

Asks:

What is the cheapest edge that connects this vertex to the growing tree?

⭐ Key Points

Students should remember these eight points:

Dijkstra solves the single-source shortest-path problem.
It works on weighted directed graphs.
All edge weights must be nonnegative.
It maintains a set S of vertices whose shortest distances are finalized.
It repeatedly selects the vertex with the smallest d value.
It uses RELAXATION to improve shortest-path estimates.
A min-priority queue makes the selection efficient.
With a binary min-heap, its standard running time is:

O((V+E)logV)

and for the usual connected/sparse-graph form:

O(ElogV)

Dijkstra's algorithm repeatedly selects the unprocessed vertex with the smallest current shortest-path estimate and relaxes its outgoing edges. Because all edge weights are nonnegative, once a vertex is selected, its shortest-path distance is final.