ften there are multiple shortest paths between two vertices in a graph. Give an
ID: 3696421 • Letter: F
Question
ften there are multiple shortest paths between two vertices in a graph. Give an O(V + E) time algorithm for the following task.
Input: An undirected graph G = (V, E) in adjacency list format; vertices u and w in V.
Output: The number of distinct shortest paths from u to w.
Note: Your algorithm should not list all the paths; just compute their number.
1. your algorithm in pseudocode. Comment your code.
2. Explain how your algorithm works and argue that it is correct.
3. Analyze the running time of your algorithm.
Explanation / Answer
Answer:
function NumShortestPath ( G , u , v )
Let Q be an empty queue
u.visited = true
u.distance = 0
u.numPaths = 1
add u to Q
while Q is not empty do
curr = Q.dequeue()
for each neighbour t of curr do
if t.visited = false then
t,visited = true
t.distance curr.distance + 1
t.NumPaths = curr.numPaths
add t to Q
else
if t.distance = curr.distance + 1 then
t.NumPaths + = curr.NumPaths
end if
end if
end for
end while
We run BFS with some extra constant work per vertex so the running time is O( m + n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.