NPTEL MOOC,JAN-FEB 2015

Week 4, Module 1

DESIGN AND ANALYSIS

OF ALGORITHMS
Shortest paths in weighted graphs

MADHAVAN MUKUND, CHENNAI MATHEMATICAL INSTITUTE

http://www.cmi.ac.in/~madhavan
Recall that
BFS and DFS are two systematic ways to explore a
graph

Both take time linear in the size of the graph with

adjacency lists

Recover paths by keeping parent information

BFS can compute shortest paths, in terms of

number of edges

DFS numbering can reveal many interesting features

Adding edge weights
Label each edge with a numbercost

Ticket price on a flight sector

Tolls on highway segment

Distance travelled between two stations

Typical time between two locations during peak

hour trac
Shortest paths
Weighted graph

G=(V,E) together with

Weight function, w : EReals

Let e1=(v0,v1), e2 = (v1,v2), , en = (vn-1,vn) be a path

from v0 to vn

Cost of the path is w(e1) + w(e2) + + w(en)

Shortest path from v0 to vn : minimum cost

Shortest paths
BFS finds path with fewest number of edges

In a weighted graph, need not be the shortest path

70
3 4
80 6
50
1 2 5 6
10 20
10 5
7
Shortest path problems
Single source

Find shortest paths from some fixed vertex, say

1, to every other vertex

Transport finished product from factory (single

source) to all retail outlets

Courier company delivers items from

distribution centre (single source) to addressees
Shortest path problems

All pairs

Find shortest paths between every pair of

vertices i and j

Railway routes, shortest way to travel between

any pair of cities
This lecture
Single source shortest paths

For instance, shortest paths from 1 to 2,3,,7

70
3 4
80 6
50
1 2 5 6
10 20
10 5
7
Single source shortest paths
Imagine vertices are oil depots, edges are pipelines

Set fire to oil depot at vertex 1

Fire travels at uniform speed along each pipeline

First oil depot to catch fire after 1 is nearest vertex

Next oil depot is second nearest vertex

Single source shortest paths
70
3 4
80 6
50
1 2 5 6
10 20
10 5
7
Single source shortest paths
70
3 4
80 6
50
1 2 5 6
10 20
t=0 10 5
7
Single source shortest paths
70
3 4
80 6
50
1 2 5 6
10 20
t=0 10 5
t = 10
7
Single source shortest paths
t = 16
70
3 4
80 6
50
1 2 5 6
10 20
t=0 10 5
t = 10
7
Single source shortest paths
t = 16
70
3 4
80 t = 30
6
50
1 2 5 6
10 20
t=0 10 5
t = 10
7
Single source shortest paths
t = 16
70
3 4
80 t = 30
6
50
1 2 5 6
10 20
t=0 10 5
t = 10
7

t = 40
Single source shortest paths
t = 16
70
3 4
80 t = 30 t = 45
6
50
1 2 5 6
10 20
t=0 10 5
t = 10
7

t = 40
Single source shortest paths
t = 16 t = 86
70
3 4
80 t = 30 t = 45
6
50
1 2 5 6
10 20
t=0 10 5
t = 10
7

t = 40
Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

70
3 4
80 6
50
1 2 5 6
10 20
10 5
7
Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

70
3 4
80 6

50
1 2 5 6
10 20

10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

70
3 4
80 6

50
1 2 5 6
10 20
0
10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

80
70
3 4
80 6

50
1 2 5 6
10 20
0 10
10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

80
70
3 4
80 6

50
1 2 5 6
10 20
0 10
10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16
70
3 4
80 6
30
50
1 2 5 6
10 20
0 10
10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16
70
3 4
80 6
30
50
1 2 5 6
10 20
0 10
10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16 86
70
3 4
80 6
30
50
1 2 5 6
10 20
0 10
10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16 86
70
3 4
80 6
30
50
1 2 5 6
10 20
0 10
10 5
7

Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16 86
70
3 4
80 6
30 80
50
1 2 5 6
10 20
0 10
10 5
7
40
Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16 86
70
3 4
80 6
30 80
50
1 2 5 6
10 20
0 10
10 5
7
40
Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16 86
70
3 4
80 6
30 45
50
1 2 5 6
10 20
0 10
10 5
7
40
Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16 86
70
3 4
80 6
30 45
50
1 2 5 6
10 20
0 10
10 5
7
40
Single source shortest paths
Compute expected time to burn of each vertex

Update this each time a new vertex burns

16 86
70
3 4
80 6
30 45
50
1 2 5 6
10 20
0 10
10 5
7
40
Algorithmically
Maintain two arrays

BurntVertices[ ], initially False for all i

ExpectedBurnTime[ ], initially for all i

For , use sum of all edge weights + 1

Set ExpectedBurnTime[1] = 0

Repeat, until all vertices are burnt

Find j with minimum ExpectedBurnTime

Set BurntVertices[j] = True

Recompute ExpectedBurnTime[k] for each neighbour k of j

Dijkstras algorithm
function ShortestPaths(s){ // assume source is s
for i = 1 to n
BV[i] = False; EBT[i] = infinity

EBT[s] = 0

for i = 1 to n
Choose u such that BV[u] == False
and EBT[u] is minimum
BV[u] = True
for each edge (u,v) with BV[v] == False
if EBT[v] > EBT[u] + weight(u,v)
EBT[v] = EBT[u] + weight(u,v)
Dijkstras algorithm
function ShortestPaths(s){ // assume source is s
for i = 1 to n
Visited[i] = False; Distance[i] = infinity

Distance[s] = 0

for i = 1 to n
Choose u such that Visited[u] == False
and Distance[u] is minimum
Visited[u] = True
for each edge (u,v) with Visited[v] == False
if Distance[v] > Distance[u] + weight(u,v)
Distance[v] = Distance[u] + weight(u,v)