4: (35 points) Design an Algorithm: Shortest Paths
This problem is from Introduction to Algorithms: A Creative Approach, by Udi Manber.
Let G = ( V, E ) be an unweighted, directed graph. Let v and w be two vertices of G.
Design an efficient algorithm that finds the number of different shortest paths (not necessarily vertex-disjoint) between v and w.
Make sure that you provide pseudocode, correctness justification and running time analysis for your algorithm.
- (12 points) Pseudocode: BFS-Count(G, s) is called once with s=v.
9 ENQUEUE(Q, s)
17 ENQUEUE(Q, v)
- b) (12 points) Correctness
- Mechanical: (4 points)
The for loops in lines 1-4 and 12-19 terminate. In lines 1-4 the loop visits each vertex (except the source) once. In lines 12-19 the loop visits each element of an adjacency list whose length is finite. The while loop in lines 10-20 terminates because each vertex is ENQUEUE’d only once and is eventually DEQUEUE’d. Arrays color, d, and nShortestPaths stay within bounds.
- ii) “As Advertised”: (8 points)
BFS-Count(G, s) uses a modified Breadth-First-Search starting at vertex s. (Note: Notationally, the vertex v inside BFS-Count should not be confused with the v in the high-level call BFS-Count(G, v)). It is similar to the BFS procedure on p. 532 of our textbook, except that the predecessor p array is not used and lines 3, 7, 16, 18, and 19 are introduced to keep track of the number of shortest paths. Upon termination of BFS-Count(G, s), for each vertex , d[x] contains the length of the shortest path from s to x. That is true due to Theorem 22.5.
We claim that, upon termination, nShortestPaths contains the number of shortest paths from s to x. This can be shown by induction, where the inductive hypothesis is that, at the end of each iteration of the while loop, nShortestPaths[v] contains the number of shortest paths from s to v discovered by BFS so far for each vertex v adjacent to u. In lines 3 and 7, each element of nShortestPaths is initialized to 0. As a base case, at the end of the first iteration of the while loop, each vertex v adjacent to s, having been WHITE, will have nShortestPaths[v]=1; this correctly represents the shortest path of length 1 from s to v. For the inductive step we consider what occurs during some iteration of the while loop. When a vertex v is first discovered, this means that the first shortest path in the BFS tree from s to v has been identified; nShortestPaths[v] is therefore set to 1 in line 16. If v has previously been encountered when we arrive at line 12, then we must check if we have just discovered a shortest path; this is done with the test in line 18. If we have discovered another shortest path, then we perform the assignment in line 19. Note that our inductive hypothesis guarantees that nShortestPaths[v] contains the number of shortest paths discovered so far from s to v and that nShortestPaths[u] contains the number of shortest paths discovered so far from s to u. Thus, the addition in line 19 yields the correctly updated number of shortest paths discovered so far from s to v. This completes the induction. Upon termination, nShortestPaths contains the number of shortest paths from s to each other vertex, which guarantees that we find the number of shortest paths from s to the original target vertex w.
- c) (11 points) Analysis: Derive the tightest upper bound that you can on the worst-case asymptotic running time of your pseudocode.
The worst-case asymptotic running time of BFS-Count(G, s) is in . This is because:
- the worst-case asymptotic running time of BFS(G, s) is in
- a constant number of operations has been removed
- a constant number of constant-time operations have been inserted, without creating new loops, function calls, or any recursion.
We will solve this using MST cycle property, which says that, “For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of all other edges of C, then this edge cannot belong to an MST.”
Now, run the following O(E+V) algorithm to test if the edge E connecting vertices u and v will be a part of some MST or not.
Run dfs from one of the end-points(either u or v) of the edge E considering only those edges that have weight less than that of E.
Case 1 If at the end of this dfs, the vertices u and v get connected, then edge E cannot be a part of some MST. This is because in this case there definitely exists a cycle in the graph with the edge E having the maximum weight and it cannot be a part of the MST(from the cycle property).
Case 2 But if at the end of the dfs u and v stay disconnected, then edge E must be the part of some MST as in this case E is not always the maximum weight edge of all the cycles that it is a part of.