Question

For all algorithm design problems, part of the grade depends on efficiency. For every graphG = (V,E), the vertex set is {1,2,··· ,n}. We use n to denote the number of vertices and m to denote number of edges. Unless otherwise stated, all graphs are represented as adjacency lists. Each problem is worth 40 points.

1. Giveanalgorithmthat,givenanundirectedgraphGandnodes,createsanarrayShortestCountin which ShortestCount[i] is the number of shortest paths from s to vertex i. Provide a proof by induction that your algorithm is correct. Derive its runtime.

   (Tip: Start with the BFS algorithm as given in the text, in which nodes are organized into layers Li based on distance from s, and update the counts as you build the tree.)

Answer 1

Method is very simple. We have to perform Breadth First Search with little modification. Here we have to modify BFS that whenever algorithm visit vertex v which is not yet completely explored from vertex u then we increment ShortestCount[v] by ShortestCount[u] because number of shortest path from s to v will increase by ShortestCount[u] once vertex u is also on the way of shortest path from s to v. In this way by the end of algorithm, we will have ShortestCount[i] for every vertex.

ALGO(G=(V,E), n)

1. For i = 1 to n

2........ShortestCount[i] = 0, Color[i] = White

3. Queue.Add(s); ShortestCount[s] = 1 //Add start vertex in Queue

4. While Queue.NotEmpty()

5.........u = Queue.dequeue() ; Set color[u] = Black

6.........For all vertices v adjacent to u with Color[v] != Black .

7................Color[v] = Brown

8...............ShortestCount[v] = ShortestCount[v] + ShortestCount[u] //increment shortest count of v by ShortestCount[u]

9. Return

Now ShortestCount[i] will store number of shortest path from s to vertex i in time O(|V|+|E|) which is time complexity of BFS.

Please comment for any clarification .