Advanced Algorithms Analysis

Shortest Paths

Chapter 24
 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)

2
 Shortest Path Problem
• 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 11
k 6
w( p )  w( vi  1 , vi ) y z
i 1

• 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
• Note: there might be multiple shortest paths from u to v
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

4
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

5
 Negative-Weight Edges
a b
• Negative-weight edges may form -4

3 4
c d g
negative-weight cycles 5
6
8
s 0
-3
y
• If such cycles are reachable from 2 3 7

e -6 f
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

6
 Negative-Weight Edges

• s  a: only one path

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

8
 Cycles
• Can shortest paths contain cycles?
• Negative-weight cycles No!
– Shortest path is not well defined
• Positive-weight cycles: No!
– 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

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

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

path from s
– If no predecessor, [v] = NIL
  induces a tree—shortest-path tree

11
 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

12
 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 After relaxation:
s s d[v]  d[u] +
u v u v w(u, v)
2 2
5 9 5 6

RELAX(u, v, w) RELAX(u, v, w)

u v u v
2 2
5 7 5 6 no change
13
 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)

14
 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

15
 Dijkstra (G, w, s)

S=<> Q=<s,t,x,z,y> S=<s> Q=<y,t,x,z>

t 1 x t x
1
  10
 
10 9
10 9
2 3 4 6
s 0 2 3 4 6
s 0
5 7
5 7
   
2 5 2
y z y z

16
 Example (cont.)
t 1 x t 1 x
8
10 14
 8 13
14
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

S=<s,y> Q=<z,t,x> S=<s,y,z> Q=<t,x>

17
 Example (cont.)

S=<s,y,z,t> Q=<x> S=<s,y,z,t,x> Q=<>

t x t 1 x
1
8 13
9 8 9
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

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

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

 Problem
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 1 w
1

1 -1
1st iteration v

d[s]=0 2nd iteration 3rd iteration 4th iteration

d[u]=1 d[w]=2 d[u]=0
d[v]=1
S={s} Q={u,v,w} S={s,u} Q={v,w} S={s,u,v} Q={w} S={s,u,v,w}
Q={}
• d[w] is not correct!
• d[u] should have converged when u was included in S!
 Dijkstra on negative weight
• Solving this graph with Dijkstra:
• Pass1 -> S=<w>, Q=<xyz> w 5 x
0 
– d[y]=4, d[x]=5
• Pass 2 -> S=<wy>, Q=<xz> 4 -6 3

– d[y]=4, d[x]= 5
• Pass 3 -> S=<wyx>, Q=<z>  
2
y z
– d[x]= 5, d[z]=8
– Selecting z results in empty Q, so algorithm
terminates
– But…
– D[y] can be set to d[x]+c[x,y] = -1 but as we have
visited y we cannot update it again!
 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.
(t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
t 5 x
 
6 -2
-3
8 7
s 0
-4
7 2
 
9
y z
 BELLMAN-FORD(V, E, w, s)

t 5 x Pass 1 t 5 x
  
6 
6 -2 6 -2
-3 -3
8 7 8 7
s 0 s 0
-4 -4
7 2 7 2
  
7 
9 9
y z y z

E: (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)
Example (t, x), (t, y), (t, z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

t 5 x t x
Pass 1 5
6  Pass 2
(from 6 
4
11
6 -2 6 -2
previous -3 -3
slide) s 0 8 7 8 7
s 0
-4 -4
7 2 7 2
7  7 2

9 9
y z y z
Pass 3 t 5 x Pass 4 t 5 x
2
6 
4
11 2
6 
4
11
6 -2 6 -2
-3 -3
8 7 8 7
s 0 s 0
-4 -4
7 2 7 2
7 2
 7 2

-2
9 9
y z y z
 BELLMAN-FORD(V, E, w, s)
1. INITIALIZE-SINGLE-SOURCE(V, s) (V)
2. for i ← 1 to |V| - 1 O(V)
O(VE)
3. do for each edge (u, v)  E O(E)
4. do RELAX(u, v, w)
5. for each edge (u, v)  E O(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)

 Detecting Negative Cycles
(perform extra test after V-1 iterations)
• for each edge (u, v)  E s b
• do if d[v] > d[u] + w(u, v) 0
2


• then return FALSE -8 3

• 
return TRUE
c
1 pass
st 2 pass
nd

s b s b Look at edge (s, b):

2 2
0
-3 
2 -6
-3 -1
2
d[b] = -1
-8 3 -8 3

5 5
2 d[s] + w(s, b) = -4
c c
 d[b] > d[s] + w(s, b)
edges: (s,b) (b,c) (c,s)
 Detecting Negative Cycles example
• Consider the following example:
w 5 x
0 

4 -6 3

 
2
y z

The graph has 4 vertices so we will iterate 3 times to find

shortest distance. And we will perform the 4th iteration to
check if there is any negative cycle.
 Assignment

• Apply |V| passes to determine negative cycle

w 5 x
0 

4 -6 3

 
2
y z

E: (w, x), (w, y), (x, z), (y, x), (z, y)

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