Shortest path algorithms

Analysis of Algorithms
Shortest Paths
Dr. AMIT KUMAR @JUET

Shortest Path Problems
• How can we find the shortest route between two
points on a road 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)

Shortest Path Problem
• Input:
– Directed graph G = (V, E)
– Weight function w : E → R
• Weight of path p = v0, v1, . . . , vk
• Shortest-path weight from u to v:
δ(u, v) = min w(p) : u v if there exists a path from u to v
∞ otherwise
• Note: there might be multiple shortest paths from u to v


k
i
ii vvwpw
1
1 ),()(
p
0
3 9
5 11
3
6
5
7
6
s
t x
y z
2
2 1
4
3

Variants of Shortest Path
• Single-source shortest paths
– G = (V, E)  find a shortest path from a given source
vertex s to each vertex v  V
• Single-destination shortest paths
– Find a shortest path to a given destination vertex t
from each vertex v
– Reversing the direction of each edge  single-source

Variants of Shortest Paths (cont’d)
• Single-pair shortest path
– Find a shortest path from u to v for given vertices u
and v
• All-pairs shortest-paths
– Find a shortest path from u to v for every pair of
vertices u and v

Negative-Weight Edges
• Negative-weight edges may form
negative-weight cycles
• If such cycles are reachable from
the source, then δ(s, v) is not properly
defined!
– Keep going around the cycle, and get
w(s, v) = -  for all v on the cycle
0
3
-4
2
8
-6
s
a b
e f
-3
y
3
5
6
4
7
c d g

• s  a: only one path
δ(s, a) = w(s, a) = 3
• s  b: only one path
δ(s, b) = w(s, a) + w(a, b) = -1
• s  c: infinitely many paths
s, c, s, c, d, c, s, c, d, c, d, c
cycle has positive weight (6 - 3 = 3)
s, c is shortest path with weight δ(s, b) = w(s, c) = 5
0
3 -1
- -
3
-4
2
8
-6
s
a b
e f
-5 11
-3
y
3
5
6
4
7
c d g

• s  e: infinitely many paths:
– s, e, s, e, f, e, s, e, f, e, f, e
– cycle e, f, e has negative
weight:
3 + (- 6) = -3
– can find paths from s to e with
arbitrarily large negative
weights
– δ(s, e) = -   no shortest path
exists between s and e
– Similarly: δ(s, f) = - ,
δ(s, g) = - 
0
3 -1
- -
3
-4
2
8
-6
s
a b
e f
-5 11
-3
y
3
5
6
4
7
c d g
 

j
h i
2
3-8
δ(s, h) = δ(s, i) = δ(s, j) = 
h, i, j not
reachable
from s

Cycles
• Can shortest paths contain cycles?
• Negative-weight cycles
– Shortest path is not well defined
• Positive-weight cycles:
– By removing the cycle, we can get a shorter path
• Zero-weight cycles
– No reason to use them
– Can remove them to obtain a path with same weight
No!
No!

Optimal Substructure Theorem
Given:
– A weighted, directed graph G = (V, E)
– A weight function w: E  R,
– A shortest path p = v1, v2, . . . , vk from v1 to vk
– A subpath of p: pij = vi, vi+1, . . . , vj, with 1  i  j  k
Then: pij is a shortest path from vi to vj
Proof: p = v1 vi vj vk
w(p) = w(p1i) + w(pij) + w(pjk)
Assume  pij’ from vi to vj with w(pij’) < w(pij)
 w(p’) = w(p1i) + w(pij’) + w(pjk) < w(p) contradiction!
p1i pij pjk
v1
vi
vj
vk
p1i
pij
pij’
pjk

Triangle Inequality
For all (u, v)  E, we have:
δ (s, v) ≤ δ (s, u) + δ (u, v)
- If u is on the shortest path to v we have the
equality sign
u v
s
v
s
u

Algorithms
• Bellman-Ford algorithm
– Negative weights are allowed
– Negative cycles reachable from the source are not
allowed.
• Dijkstra’s algorithm
– Negative weights are not allowed
• Operations common in both algorithms:
– Initialization
– Relaxation

Shortest-Paths Notation
For each vertex v  V:
• δ(s, v): shortest-path weight
• d[v]: shortest-path weight estimate
– Initially, d[v]=∞
– d[v]δ(s,v) as algorithm progresses
• [v] = predecessor of v on a shortest
path from s
– If no predecessor, [v] = NIL
–  induces a tree—shortest-path tree
0
3 9
5 11
3
6
5
7
6
s
t x
y z
2
2 1
4
3

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

Relaxation Step
• 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
 d[v]=d[u]+w(u,v)
 [v] ← u
5 9
2
u v
5 7
2
u v
RELAX(u, v, w)
5 6
2
u v
5 6
2
u v
RELAX(u, v, w)
After relaxation:
d[v]  d[u] + w(u, v)s s
no change

Bellman-Ford Algorithm
• Single-source shortest path problem
– Computes δ(s, v) and [v] for all v  V
• Allows negative edge weights - can detect
negative cycles.
– Returns TRUE if no negative-weight cycles are
reachable from the source s
– Returns FALSE otherwise  no solution exists

Bellman-Ford Algorithm (cont’d)
• Idea:
– Each edge is relaxed |V–1| times by making |V-1|
passes over the whole edge set.
– To make sure that each edge is relaxed exactly
|V – 1| times, it puts the edges in an unordered list
and goes over the list |V – 1| times.
0
 
 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

BELLMAN-FORD(V, E, w, s)
0
 
 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
0
 
 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
E: (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
6
7
Pass 1

Example
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
11
2
4
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
11
2
42
0
6 
7 
6
5
7
7
9
s
t x
y z
8
-3
2
-4
-2
11
2
42
-2
Pass 1
(from
previous
slide)
Pass 2
Pass 3 Pass 4

Detecting Negative Cycles
(perform extra test after V-1 iterations)
• for each edge (u, v)  E
• do if d[v] > d[u] + w(u, v)
• then return FALSE
• return TRUE
0 

c
s b
2
3-8
0 

c
s b
2
3-8
2
5
-3 -3 2
5
c
s b
2
3-8
-1
2
-6
Look at edge (s, b):
d[b] = -1
d[s] + w(s, b) = -4
 d[b] > d[s] + w(s, b)
1st pass 2nd pass
(s,b) (b,c) (c,s)

BELLMAN-FORD(V, E, w, s)
1. INITIALIZE-SINGLE-SOURCE(V, s)
2. for i ← 1 to |V| - 1
3. do for each edge (u, v)  E
4. do RELAX(u, v, w)
5. for each edge (u, v)  E
6. do if d[v] > d[u] + w(u, v)
7. then return FALSE
8. return TRUE
Running time: O(V+VE+E)=O(VE)
(V)
O(V)
O(E)
O(E)
O(VE)

Shortest Path Properties
• Upper-bound property
– We always have d[v] ≥ δ (s, v) for all v.
– The estimate never goes up – relaxation only lowers the
estimate
0
6 
7 
6
5
7
7
9
s
v x
y z
8
-3
2
-4
-2
11
2
4
0
6 
7 
6
5
7
7
9
s
v x
y z
8
-3
2
-4
-2
11
2
42
Relax (x, v)

• Convergence property
If s u → v is a shortest path, and if d[u] = δ(s, u)
at any time prior to relaxing edge (u, v), then
d[v] = δ(s, v) at all times after relaxing (u, v).
0
6 
7
5
2
4
s
u v
1185
4
• If d[v] > δ(s, v)  after relaxation:
d[v] = d[u] + w(u, v)
d[v] = 5 + 2 = 7
• Otherwise, the value remains
unchanged, because it must have
been the shortest path value

• Path relaxation property
Let p = v0, v1, . . . , vk be a shortest path from
s = v0 to vk. If we relax, in order, (v0, v1), (v1, v2), . . .
, (vk-1, vk), even intermixed with other relaxations,
then d[vk ] = δ (s, vk).
0
6 

5
2
4
s
v1 v2
11

3
5 7
11
14
d[v1] = δ (s, v1)
d[v2] = δ (s, v2)
d[v3] = δ (s, v3)
d[v4] = δ (s, v4)
v3
v4

Correctness of Belman-Ford Algorithm
• Theorem: Show that d[v]= δ (s, v), for every v,
after |V-1| passes.
Case 1: G does not contain negative cycles
which are reachable from s
– Assume that the shortest path from s to v is
p = v0, v1, . . . , vk, where s=v0 and v=vk, k≤|V-1|
– Use mathematical induction on the number of
passes i to show that:
d[vi]= δ (s, vi) , i=0,1,…,k

(cont.)
Base Case: i=0 d[v0]= δ (s, v0)= δ (s, s)= 0
Inductive Hypothesis: d[vi-1]= δ (s, vi-1)
Inductive Step: d[vi]= δ (s, vi)
w
vi-1 vi
s
d[vi-1]= δ (s, vi-1)
From the upper bound property: d[vi]≥ δ (s, vi)
Therefore, d[vi]=δ (s, vi)
After relaxing (vi-1, vi):
d[vi]≤d[vi-1]+w= δ (s, vi-1)+w= δ (s, vi)

(cont.)
• Case 2: G contains a negative cycle which is
reachable from s
<0
d d
d d
d dProof by
Contradiction:
suppose the
algorithm
returns a
solution
Contradiction!

Dijkstra’s Algorithm
• Single-source shortest path problem:
– No negative-weight edges: w(u, v) > 0,  (u, v)  E
• Each edge is relaxed only once!
• Maintains two sets of vertices:
d[v]=δ (s, v) d[v]>δ (s, v)

Dijkstra’s Algorithm (cont.)
• Vertices in V – S reside in a min-priority queue
– Keys in Q are estimates of shortest-path weights d[u]
• Repeatedly select a vertex u  V – S, with the
minimum shortest-path estimate d[u]
• Relax all edges leaving u

Dijkstra (G, w, s)
0
 
 
10
1
5
2
s
t x
y z
2 3
9
7
4 6
0
 
 
10
1
5
2
s
t x
y z
2 3
9
7
4 6
10
5
S=<> Q=<s,t,x,z,y> S=<s> Q=<y,t,x,z>

Example (cont.)
0
10 
5 
10
1
5
2
s
t x
y z
2 3
9
7
4 6
8 14
7
0
8 14
5 7
10
1
5
2
s
t x
y z
2 3
9
7
4 6
13
S=<s,y> Q=<z,t,x> S=<s,y,z> Q=<t,x>

Example (cont.)
0
8 13
5 7
10
1
5
2
s
t x
y z
2 3
9
7
4 6
9
0
8 9
5 7
10
1
5
2
s
t x
y z
2 3
9
7
4 6
S=<s,y,z,t> Q=<x> S=<s,y,z,t,x> Q=<>

Dijkstra (G, w, s)
1. INITIALIZE-SINGLE-SOURCE(V, s)
2. S ← 
3. Q ← V[G]
4. while Q  
5. do u ← EXTRACT-MIN(Q)
6. S ← S  {u}
7. for each vertex v  Adj[u]
8. do RELAX(u, v, w)
9. Update Q (DECREASE_KEY)
Running time: O(VlgV + ElgV) = O(ElgV)
(V)
O(V) build min-heap
Executed O(V) times
O(lgV)
O(E) times
(total)
O(lgV)
O(VlgV)
O(ElgV)

Binary Heap vs Fibonacci Heap
Running time depends on the implementation of the heap

Correctness of Dijskstra’s Algorithm
• For each vertex u  V, we have d[u] = δ(s, u) at the time
when u is added to S.
Proof:
• Let u be the first vertex for which d[u]  δ(s, u) when
added to S
• Let’s look at a true shortest path p from s to u:

Correctness of Dijskstra’s Algorithm
Since u’ is in the shortest path of u: d[u’]<δ(s,u)
What is the value of d[u’]?
d[u’]≤d[v’]+w(v’,u’)= δ(s,v’)+w(v’,u’)
What is the value of d[u]?
d[u]≤d[v]+w(v,u)= δ(s,v)+w(v,u)
Using the upper bound property: d[u]>δ(s,u)
d[u’]<d[u]
Priority Queue Q: <u, …, u’, ….> (i.e., d[u]<…<d[u’]<… )
Contradiction!

All-Pairs Shortest Paths
• Given:
– Directed graph G = (V, E)
– Weight function w : E → R
• Compute:
– The shortest paths between all pairs
of vertices in a graph
– Result: an n × n matrix of shortest-
path distances δ(u, v)
1
2
3
5 4
3
-4 7
6
2
4
1
-5
8

All-Pairs Shortest Paths - Solutions
• Run BELLMAN-FORD once from each vertex:
– O(V2E), which is O(V4) if the graph is dense
(E = (V2))
• If no negative-weight edges, could run
Dijkstra’s algorithm once from each vertex:
– O(VElgV) with binary heap, O(V3lgV) if the graph is
dense
• We can solve the problem in O(V3), with no
elaborate data structures

Application: Feasibility Problem

Application: Feasibility Problem (cont.)

x1 x2
x3
x4
x5
0
-1
1
5
4
-1
-3
-3
x0
0
0
0
0
0

Theorem: If G contains no negative cycles, then
(δ(v0,v1), δ(v0,v2),…, δ(v0,vn)) is a feasible solution.
For every (vi, vj): δ(v0,vj)≤ δ(v0,vi)+w(vi,vj)
or δ(v0,vj) - δ(v0,vi) ≤ w(vi,vj)
Setting xi= δ(v0,vi) and xj= δ(v0,vj), we have
xj-xi≤ w(vi,vj)

• Theorem: If G contains a negative cycle, then
there is no feasible solution.
Proof by contradiction: suppose
there exist a solution, then:

Problem 1
Write down weights for the edges of the following graph,
so that Dijkstra’s algorithm would not find the correct
shortest path from s to t.
s u
v
w1
1
1
-1
d[s]=0
d[u]=1
d[v]=1
S={s} Q={u,v,w}
d[w]=2
S={s,u} Q={v,w}
d[u]=0
S={s,u,v} Q={w}
1st iteration
2nd iteration 3rd iteration 4th iteration
S={s,u,v,w}
Q={}
• d[w] is not correct!
• d[u] should have converged when u was included in S!

Problem 2
• (Exercise 24.3-4, page 600) We are given a
directed graph G=(V,E) on which each edge
(u,v) has an associated value r(u,v), which is a
real number in the range 0≤r(u,v) ≤1 that
represents the reliability of a communication
channel from vertex u to vertex v.
• We interpret r(u,v) as the probability that the
channel from u to v will not fail, and we assume
that these probabilities are independent.
• Give an efficient algorithm to find the most
reliable path between two given vertices.

Problem 2 (cont.)
• Solution 1: modify Dijkstra’s algorithm
– Perform relaxation as follows:
if d[v] < d[u] w(u,v) then
d[v] = d[u] w(u,v)
– Use “EXTRACT_MAX” instead of “EXTRACT_MIN”

Problem 2 (cont.)
• Solution 2: use Dijkstra’s algorithm without any
modifications!
– r(u,v)=Pr( channel from u to v will not fail)
– Assuming that the probabilities are independent, the
reliability of a path p=<v1,v2,…,vk> is:
r(v1,v2)r(v2,v3) … r(vk-1,vk)
– We want to find the channel with the highest
reliability, i.e.,
( , )
max ( , )p
u v p
r u v



Problem 2 (cont.)
• But Dijkstra’s algorithm computes
• Take the lg
( , )
min ( , )p
u v p
w u v


( , )( , )
lg(max ( , )) max lg( ( , ))p p
u v pu v p
r u v r u v

 

Problem 2 (cont.)
• Turn this into a minimization problem by taking
the negative:
• Run Dijkstra’s algorithm using
( , ) ( , )
min lg( ( , )) min lg( ( , ))p p
u v p u v p
r u v r u v
 
   
( , ) lg( ( , ))w u v r u v 

Shortest path algorithms

Recommended

More Related Content

What's hot (20)

Similar to Shortest path algorithms (20)

More from Amit Kumar Rathi (20)

Recently uploaded (20)

Shortest path algorithms