Shortest Path

Single Source Shortest Path

(Dijkstra’s Algorithm)
 Shortest Path Problems
• What is shortest path ?
▪ shortest length between two vertices for an
unweighted graph:
▪ smallest cost between two vertices for a weighted
graph:
B 210 B

A A
450
60 190

C unweighted C weighted
graph graph
200 130
D D
E E
 Example 
Source node-A
4
Destination node-F
A B 9
5
5
8 E F
6 2
3
C 2
D

10
Steps:
⮚Find the shortest path between two vertices in a graph
⮚Calculate all vertices from the graph

6
 Example Cont.
4
A B 9
5
5 8 E 2 F
6 3
C D
2
10
Path Weight Result
A-B-E-F 4+9+2 15
A-B-D-E-F 4+8+3+2 17 Finally the minimum
A-B-C-D-E-F 4+6+2+3+2 17 shortest path,
A-B-C-D-B-E-F 4+6+2+8+9+2 31
A-C-D-E-F 5+2+3+2 12 A-D-E-F = 10
A-C-F 5+10 15
A-D-E-F 5+3+2 10
A-D-B-E-F 5+8+9+2 24
A-C-D-B-E-F 5+2+8+9+2 26
7
 Shortest Path Problems
• How can we find the shortest route between two
points on a map?
• Model the problem as a graph problem:
– Road map is a weighted graph:
vertices = cities
edges = road segments between cities
edge weights = road distances
– Goal: find a shortest path between two vertices (cities)

5
 Shortest Path Problems
• Input: t x
6
3 9
– Directed graph G = (V, E) 3
4
2 1
– Weight function w : E → R s 0
2 7
5 3
• Weight of path p = 〈 v0, v1, . . . , vk 〉 5
1
6 1
y z

• Shortest-path weight from u to v:

p
δ(u, v) = min w(p) : u v if there exists a path from u to v
∞ otherwise
• Shortest path u to v is any path p such that w(p) = δ(u, v)
6
 Variants of Shortest Paths
• Single-source shortest path
– G = (V, E) ⇒ find a shortest path from a given source vertex s to
each vertex v ∈ V
• Single-destination shortest path
– Find a shortest path to a given destination vertex t from each
vertex v
– Reverse the direction of each edge ⇒ single-source
• Single-pair shortest path
– Find a shortest path from u to v for given vertices u and v
– Solve the single-source problem
• All-pairs shortest-paths
– Find a shortest path from u to v for every pair of vertices u and v

7
 Shortest-Path Representation
For each vertex v ∈ V:
t x
• d[v] = δ(s, v): a shortest-path estimate 3
6
9
– Initially, d[v]=∞ 3
4
2 1
– Reduces as algorithms progress s 0
2 7
5 3
• π[v] = predecessor of v on a shortest 5
1
6 1
path from s y z

– If no predecessor, π[v] = NIL

– π induces a tree—shortest-path tree
• Shortest paths & shortest path trees are
not unique
8
 Initialization
Alg.: INITIALIZE-SINGLE-SOURCE(V, s)
1. for each v ∈ V
2. do d[v] ← ∞
3. π[v] ← NIL
4. d[s] ← 0

• All the shortest-paths algorithms start with

INITIALIZE-SINGLE-SOURCE

9
 Relaxation
• Relaxing an edge (u, v) = testing whether we
can improve the shortest path to v found so far
by going through u
If d[v] > d[u] + w(u, v)
we can improve the shortest path to v
⇒ update d[v] and π[v]
s s
u v u v
5
2
9
2 After relaxation:
5 6
d[v] ≤ d[u] + w(u, v)
RELAX(u, v, w) RELAX(u, v, w)

u v u v
2 2
5 7 5 6
10
 RELAX(u, v, w)
1. if d[v] > d[u] + w(u, v)
2. then d[v] ← d[u] + w(u, v)
3. π[v] ← u

• All the single-source shortest-paths algorithms

– start by calling INIT-SINGLE-SOURCE
– then relax edges
• The algorithms differ in the order and how
many times they relax each edge

11
 Dijkstra’s Algorithm
• Single-source shortest path problem:
– No negative-weight edges: w(u, v) > 0 ∀ (u, v) ∈ E

• Maintains two sets of vertices:

– S = vertices whose final shortest-path weights have
already been determined
– Q = vertices in V – S: min-priority queue
• Keys in Q are estimates of shortest-path weights (d[v])

• Repeatedly select a vertex u ∈ V – S, with the

minimum shortest-path estimate d[v]
12
 Dijkstra (G, w, s)
t 1 x
1. INITIALIZE-SINGLE-SOURCE(V, s) ∞ ∞
10 9
2. S ← ∅ s 0
2 3 4 6

3. Q ← V[G] 5 7
∞ ∞
4. while Q ≠ ∅ y
2
z
t x
5. do u ← EXTRACT-MIN(Q) 1
∞
1
∞
0 9
10
6. S ← S ∪ {u}
2 3 4 6
s 0
7. for each vertex v ∈ Adj[u] 5 7

8. do RELAX(u, v, w) ∞
5 2
∞
y z

13
 Example
t 1 x t 1 x
1 1 11
8 ∞ 8
0 4 43
10 9 10 9
2 3 4 6 2 3 4 6
s 0 s 0
5 7 5 7
5 7
∞ 5 7
2 2
y z y z

t x t 1 x
1
1 8 9
8 9
3 10 9
10 9
2 4 2 3 4 6
s 0 3 6 s 0

7 5 7
5
5 7 5 7
2 2
y z y z
14
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
 Exercise 1

Find the shortest path to every vertices on this graph

Solution
 An Example
∞ ∞
4
2 4
2 2
0
1 1 2 6 ∞
4 3
2

3 3 5
∞ ∞

Initialize

Select the node with the

minimum temporary distance
label.
 Update Step
2
∞ ∞
2 4 4
2 2
0
1 2 6 ∞
1 3
4 2

3 3 5
∞ ∞
4
Choose Minimum Temporary Label
2 ∞
2 4 4
2 2
0
1 2 6 ∞
1 3
4 2

3 3 5
4 ∞
 Update Step
6
2 ∞
2 4 4
2 2
0
1 2 6 ∞
1 3
4 2

3 3 5
4 ∞

3 4

The predecessor of
node 3 is now node 2
Choose Minimum Temporary Label
2 6
2 4 4
2 2
0
1 2 6 ∞
1 3
4 2

3 3 5
3 4
 Update
2 6
2 4 4
2 2
0
1 2 6 ∞
1 3
4 2

3 3 5
3 4

d(5) is not changed.

Choose Minimum Temporary Label
2 6
2 4 4
2 2
0
1 2 6 ∞
1 3
4 2

3 3 5
3 4
 Update
2 6
2 4 4
2 2
0
6
1 2 6 ∞
1 3
4 2

3 3 5
3 4

d(4) is not changed

Choose Minimum Temporary Label
2 6
2 4 4
2 2
0
1 2 6 6
1 3
4 2

3 3 5
3 4
 Update
2 6
2 4 4
2 2
0
1 2 6 6
1 3
4 2

3 3 5
3 4

d(6) is not updated

Choose Minimum Temporary Label
2 6
2 4 4
2 2
0
1 2 6 6
1 3
4 2

3 3 5
3 4

There is nothing to update

 End of Algorithm
2 6
2 4 4
2 2
0
1 2 6 6
1 3
4 2

3 3 5
3 4

All nodes are now permanent

The predecessors form a tree

The shortest path from node 1 to node 6 can be found by

tracing back predecessors
 Dijkstra’s Pseudo Code
• Graph G, weight function w, root s

relaxing
edges
DIJKSTRA'S ALGORITHM - WHY USE IT?

• As mentioned, Dijkstra’s algorithm calculates the

shortest path to every vertex.
• However, it is about as computationally expensive
to calculate the shortest path from vertex u to every
vertex using Dijkstra’s as it is to calculate the
shortest path to some particular vertex v.
• Therefore, anytime we want to know the optimal
path to some other vertex from a determined origin,
we can use Dijkstra’s algorithm.
 Applications of Dijkstra's Algorithm
- Traffic Information Systems are most prominent use 
- Mapping (Map Quest, Google Maps)
- Routing Systems
 Applications of Dijkstra's Algorithm
🞆 One particularly relevant this
week: epidemiology
🞆 Prof. Lauren Meyers (Biology
Dept.) uses networks to model the
spread of infectious diseases and
design prevention and response
strategies.
🞆 Vertices represent individuals,
and edges their possible contacts.
It is useful to calculate how a
particular individual is connected to
others.
🞆 Knowing the shortest path
lengths to other individuals can be
a relevant indicator of the potential
of a particular individual to infect
others.
 Dijkstra (G, w, s)
1. INITIALIZE-SINGLE-SOURCE(V, s) Θ(V
2. S← ∅ )
3. Q ← V[G] O(V)
4. while Q ≠ ∅ Executed O(V)
5. times
do u ← EXTRACT-MIN(Q) O(lgV) O(VlgV)

6. S ← S ∪ {u}
7. for each vertex v ∈ Adj[u] O(E) times
8. do RELAX(u, v, w) (total) O(ElgV)
9. Update Q (DECREASE_KEY) O(lgV)

Running time: O(VlgV + ElgV) = O(ElgV) 42

 Question
• Prove that, if there exists negative edge, dijkstra’s
shortest path algorithm may fail to find the shortest path
• Print the shortest path for dijkstra’s algorithm
• How many shortest paths are there from source to
destination?
• Suppose you are given a graph where each edge
represents the path cost and each vertex has also a cost
which represents that, if you select a path using this
node, the cost will be added with the path cost. How can
it be solved using Dijkstra’s algorithm?

43
 Question
• How to solve ACM534 – Frogger?

44