SINGLE-SOURCE SHORTEST PATHS

Shortest Path Problems

• Directed weighted graph.
• Path length is sum of weights of edges on path.
• The vertex at which the path begins is the source vertex.
• The vertex at which the path ends is the destination vertex.

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

14

• Consider Source node 1 and destination node 7

• A direct path between Nodes 1 and 7 will cost 14
 Example
8 6
1
2 3
3 1
16
6 7 4 5 10
4
2 4 7
5 3

14

• A shorter path will cost only 11

 Shortest-Path Variants
• Single-source single-destination (1-1): Find the shortest
path from source s to destination v.

• Single-source all-destination(1-Many): Find the shortest

path from s to each vertex v.

• Single-destination shortest-paths (Many-1): Find a shortest

path to a given destination vertex t from each vertex v.

• All-pairs shortest-paths problem (Many-Many): Find a

shortest path from u to v for every pair of vertices u and v.

We talk about directed, weighted graphs

 Shortest-Path Variants (Cont’d)
• For un-weighted graphs, the shortest path problem is mapped to BFS
– Since all weights are the same, we search for the smallest number of edges

BFS creates a tree called BFS-Tree

1 2 3
2 4 8

0 s 5 7
1 3

3 6 9

1 2 3
 Shortest-Path Variants
No need to consider different solution or algorithm for each variant
(we reduce it into two types)

• Single-source single-destination (1-1): Find the shortest

path from source s to destination v.

• Single-source all-destination(1-Many): Find the shortest

path from s to each vertex v.

• Single-destination shortest-paths (Many-1): Find a shortest

path to a given destination vertex t from each vertex v.

• All-pairs shortest-paths problem (Many-Many): Find a

shortest path from u to v for every pair of vertices u and v.
Shortest-Path Variants

Single-Source Single-Destination (1-1) Single-Source All-Destination (1-M)

-No good solution that beats 1-M variant -Need to be solved (several algorithms)
-Thus, this problem is mapped to the 1-M -We will study this one
variant

All-Sources Single-Destination (M-1) All-Sources All-Destinations (M-M)

-Reverse all edges in the graph -Need to be solved (several algorithms)

-Thus, it is mapped to the (1-M) variant -We will study it (if time permits)
Shortest-Path Variants

Single-Source Single-Destination (1-1) Single-Source All-Destination (1-M)

-No good solution that beats 1-M variant -Need to be solved (several algorithms)
-Thus, this problem is mapped to the 1-M -We will study this one
variant

All-Sources Single-Destination (M-1) All-Sources All-Destinations (M-M)

-Reverse all edges in the graph -Need to be solved (several algorithms)

-Thus, it is mapped to the (1-M) variant -We will study it (if time permits)
 Introduction

Generalization of BFS to handle weighted graphs

• Direct Graph G = ( V, E ), edge weight fn ; w : E → R
• In BFS w(e)=1 for all e  E

Weight of path p = v1  v2  …  vk is
k 1
w( p)   w(vi , vi 1 )
i 1
 Shortest Path
Shortest Path = Path of minimum weight

δ(u,v)=

p
min{ω(p) : u v}; if there is a path from u to v,
 otherwise.
Several Properties
 1- Optimal Substructure Property

Theorem: Subpaths of shortest paths are also shortest paths

• Let δ(1,k) = <v1, ..i, .. j.., .. ,vk > be a shortest path from v1 to vk
• Let δ(i,j) = <vi, ... ,vj > be subpath of δ(1,k) from vi to vj
for any i, j
• Then δ(I,j) is a shortest path from vi to vj
 1- Optimal Substructure Property

Proof: By cut and paste

v0 v1 v2 v3 v4 v5 v6 v7

• If some subpath were not a shortest path

• We could substitute a shorter subpath to create a shorter
total path
• Hence, the original path would not be shortest path
 2- No Cycles in Shortest Path
Definition:
• δ(u,v) = weight of the shortest path(s) from u to v

• Negative-weight cycle: The problem is undefined

– can always get a shorter path by going around the cycle again

cycle
<0
s v
• Positive-weight cycle : can be taken out and reduces the cost
 3- Negative-weight edges

• No problem, as long as no negative-weight cycles are

reachable from the source (allowed)
 4- Triangle Inequality
Lemma 1: for a given vertex s in V and for every edge (u,v)  E,
• δ(s,v) ≤ δ(s,u) + w(u,v)

Proof: shortest path s v is no longer than any other path.

• in particular the path that takes the shortest path s v and
then takes cycle (u,v)

u v

s
 Algorithms to Cover

• Dijkstra’s Algorithm

• Shortest Path is DAGs

 Initialization

• Maintain d[v] for each v in V

• d[v] is called shortest-path weight estimate
and it is upper bound on δ(s,v)
INIT(G, s)
for each v  V do Upper bound

d[v] ← ∞
π[v] ← NIL Parent node

d[s] ← 0
 Relaxation
When you find an edge (u,v) then
RELAX(u, v) check this condition and relax d[v] if
if d[v] > d[u]+w(u,v) then possible

d[v] ← d[u]+w(u,v)
π[v] ← u
u v u v
2 2
   
Change d[v] No chnage

 2   2 
u v u v
 Algorithms to Cover

• Dijkstra’s Algorithm

• Shortest Path is DAGs

Dijkstra’s Algorithm For Shortest Paths
• Non-negative edge weight

• Like BFS: If all edge weights are equal, then use BFS,
otherwise use this algorithm

• Use Q = min-priority queue keyed on d[v] values

Dijkstra’s Algorithm For Shortest Paths
DIJKSTRA(G, s)
INIT(G, s)
S←Ø > set of discovered nodes
Q←V[G]
while Q ≠Ø do
u←EXTRACT-MIN(Q)
S←S U {u}
for each v in Adj[u] do
RELAX(u, v) > May cause
> DECREASE-KEY(Q, v, d[v])
 Example: Initialization Step

DIJKSTRA(G, s)
u v
INIT(G, s)
1
S←Ø > set of discovered nodes ¥ ¥
10
Q←V[G]
2 3 9
while Q ≠Ø do s 0 4 6
u←EXTRACT-MIN(Q) 7
5
S←S U {u} ¥ ¥
2
for each v in Adj[u] do
x y
RELAX(u, v) > May cause
> DECREASE-KEY(Q, v, d[v])
 Example
u v
1
 
10
2 3 9
s  4 6
7
5
 2 
x y
 Example
DIJKSTRA(G, s) u v
INIT(G, s)
1
S←Ø > set of discovered nodes  
Q←V[G] 10
9
while Q ≠Ø do
2 3
u←EXTRACT-MIN(Q) s 4 6
S←S U {u} 
for each v in Adj[u] do 7
RELAX(u, v) > May cause 5
> DECREASE-KEY(Q, v, d[v])  2 
x y
 Example
u v
DIJKSTRA(G, s)
INIT(G, s) 1
S←Ø > set of discovered nodes
 
10
Q←V[G]
while Q ≠Ø do 2 3 9
u←EXTRACT-MIN(Q) s  4 6
S←S U {u}
for each v in Adj[u] do 7
5
RELAX(u, v) > May cause
> DECREASE-KEY(Q, v, d[v])  2

x y
 Example
DIJKSTRA(G, s) u v
INIT(G, s) 1
S←Ø > set of discovered nodes  
10
Q←V[G]
while Q ≠Ø do 2 3 9
u←EXTRACT-MIN(Q) s  4 6
S←S U {u}
for each v in Adj[u] do 7
5
RELAX(u, v) > May cause
> DECREASE-KEY(Q, v, d[v])
 2 
x y
 Example
DIJKSTRA(G, s) u v
INIT(G, s) 1
S←Ø > set of discovered nodes  
Q←V[G] 10
while Q ≠Ø do
2 3 9
u←EXTRACT-MIN(Q) s
S←S U {u}
 4 6
for each v in Adj[u] do 7
RELAX(u, v) > May cause
5
> DECREASE-KEY(Q, v, d[v])  2 
x y
 Example
u v
1
 
10
2 3 9
s  4 6
7
5
 2

x y
 Dijkstra’s Algorithm Analysis
O(V)
DIJKSTRA(G, s)
INIT(G, s)
S←Ø > set of discovered nodes
Q←V[G] O(V Log V)
while Q ≠Ø do
u←EXTRACT-MIN(Q) Total in the loop: O(V Log V)
S←S U {u}
for each v in Adj[u] do
RELAX(u, v) > May cause
> DECREASE-KEY(Q, v, d[v])
Total in the loop: O(E Log V)

Time Complexity: O (E Log V)

 Algorithms to Cover

• Dijkstra’s Algorithm

• Shortest Path is DAGs

 Key Property in DAGs

• If there are no cycles  it is called a DAG

• In DAGs, nodes can be sorted in a linear order such that all

edges are forward edges
– Topological sort
 Single-Source Shortest Paths in DAGs

• Shortest paths are always well-defined in dags

 no cycles => no negative-weight cycles even if
there are negative-weight edges

• Idea: If we were lucky

 To process vertices on each shortest path from left
to right, we would be done in 1 pass
 Single-Source Shortest Paths in DAGs
DAG-SHORTEST PATHS(G, s)
TOPOLOGICALLY-SORT the vertices of G
INIT(G, s)
for each vertex u taken in topologically sorted order do
for each v in Adj[u] do
RELAX(u, v)
 Example
6 1
r s t u v w
5 2 7 –1 –2
 0    

4
3
2
 Example
6 1
r s t u v w
5 2 7 –1 –2
 0    

4
3
2
 Example
6 1
r s t u v w
5 2 7 –1 –2
 0 2 6  

4
3
2
 Example
6 1
r s t u v w
5 2 7 –1 –2
 0 2 6 6 4

4
3
2
 Example
6 1
r s t u v w
5 2 7 –1 –2
 0 2 6 5 4

4
3
2
 Example
6 1
r s t u v w
5 2 7 –1 –2
 0 2 6 5 3

4
3
2
 Example
6 1
r s t u v w
5 2 7 –1 –2
 0 2 6 5 3

4
3
2
 Single-Source Shortest Paths in
DAGs: Analysis
O(V+E)
DAG-SHORTEST PATHS(G, s)
TOPOLOGICALLY-SORT the vertices of G
INIT(G, s) O(V)
for each vertex u taken in topologically sorted order do
for each v in Adj[u] do
RELAX(u, v) Total O(E)

Time Complexity: O (V + E)