Shortest Path

Shortest Path Graph represents highway system  Edges have weights  Length of a path is sum of weights of edges along path  Starting vertex is source, ending vertex is destination  One way streets are possible; digraph  Weights are positive 

© MMII JW Ryder

CS 428 Computer Networks

1

Single Source All Destinations Directed Graph, G = (V, E)  Weighting function w(e), w(e) > 0  Source vertex is V0 

© MMII JW Ryder

CS 428 Computer Networks

2

Patterns 

Shortest path from V0 to all other vertices



V0 to V1



Greedy algorithm to generate shortest paths S is set of vertices whose shortest paths have been found For w not is S, distance[w] is length of shortest path starting from V0 going through vertices only in S and ending at w Generate paths in non-decreasing order of lengths







© MMII JW Ryder

CS 428 Computer Networks

3

Observation 1 

If the next shortest path is to vertex u, then the path from V0 to u goes through only those vertices that are in S  Let’s show all intermediate vertices on the shortest path from V0 to u are already in S  



 

Assume (falsely) that vertex w on path is not in S We know path from V0 to u must go through w and the length from V0 to w must be less than length from V0 to u Since paths created in non-decreasing order we must have generated path to w before u This is a contradiction! Ergo cannot be any intermediate vertex that is not in S

© MMII JW Ryder

CS 428 Computer Networks

4

Observation 2 



Vertex u is chosen so that it has the minimum distance among all vertices not in S If several vertices with same distance the choice is not important

© MMII JW Ryder

CS 428 Computer Networks

5

Observation 3 

Once u is selected and the shortest path has been generated from V0 to u, u becomes a member of S



Adding u to S can change the shortest paths starting at V0 , going through vertices only in S, and ending at vertex w that is not currently in S If distance changes, we have found a shorter path from V0 to w passing through u







Intermediate vertices are in S, sub-path from u to w can be chosen so that there are no intermediate vertices The length of the shorter path is distance[u] + length()

© MMII JW Ryder

CS 428 Computer Networks

6

Who made these Observations? 

Observations and Algorithm credited to Edsger Dijkstra

© MMII JW Ryder

CS 428 Computer Networks

7

Mechanics  

n vertices numbered from 0 to n-1 Set S maintained as an array with name found[ ] 



found[i] = TRUE (1) if vertex i in S else FALSE (0)

Graph represented by its cost adjacency matrix cost [i][j] = weight of edge  If edge not in G set cost [i][j] to some large number 

   © MMII JW Ryder

Choice of number is arbitrary but can’t overflow sign Must be > any other number in matrix distance [u] + cost [u][w] can’t produce overflow CS 428 Computer Networks

8

Shortest Path Parameters 

Draw distance [ ], found [ ], cost [ ] [ ], n, v for figure below 45 50 V0 20

10 V2

V1 15 20

35

V4 30

V3 15

© MMII JW Ryder

10

V5 3

CS 428 Computer Networks

9

Basic Idea with Words -Initialize set S to Empty, distance[ ] to the distances for the source vertex from cost matrix - Put v into S; Make sure distance to self is 0 - For i = 0 to Number of Vertices in G - 2 do -Choose next vertex u to add to S. Is vertex from the set E-S with shortest distance - Add u to S - For w = each vertex in G // 0 .. n-1 if w is not already in S if distance from v to u then to w < current shortest to w Make shortest distance from v through u to w for distance [w] endif endif © MMII JW Ryder

endfor endfor CS 428 Computer Networks

10

choose ( ) int choose (int distance [ ], int n, short int found [ ] ) { // Find smallest distance not yet checked int i, min, minpos; min = INT_MAX; minpos = -1; for (i = 0; i < n; i++) if (distance [i] < min && !found [i]) { min = distance [i]; minpos = i; } return minpos; } // end choose ( ) © MMII JW Ryder

CS 428 Computer Networks

11

shortestpath ( ) void shortestpath (int v, int cost [ ][MAX_VERTICES], int found [ ])

int distance [ ], int n, short

{ // distance [i] is shortest path from vertex v to i, found [i] holds a 0 if shortest path for vertex i has not been found else 1, cost is the cost adjacency matrix int i, u, w; for (i = 0; i < n; i++) {

// Initialize part

found [i] = FALSE; distance [i] = cost [v][i]; } // end for found [v] = TRUE; distance [v] = 0; See Part Two on the Next Page © MMII JW Ryder

CS 428 Computer Networks

12

Part Two for (i = 0; i < n-2; i++) { u = choose (distance, n, found); // Pick next vertex to add to S found [u] = TRUE; // Add it to S for (w = 0; w < n; w++) { // Check all vertices adjacent to if (!found [w]) // u but not yet in S if (distance [u] + cost [u][w] < distance [w]) distance [w] = distance [u] + cost [u][w]; } // end for } // end for

© MMII JW Ryder

CS 428 Computer Networks

13

Shortest Path Analysis   

O(n2) n vertices, adjacency matrix First for loop takes O(n) Second for loop executed n-2 times - O(n) 

This loop needs O(n) - each execution  





choose () - O(n) Update distance [ ] - O(n)

Total time needed is O(n2)

Each edge in G examined at least once O(e) 

Minimum possible with cost adjacency O(n2)

© MMII JW Ryder

CS 428 Computer Networks

14