BFS modification for shortest paths
I was given the following task as an assignment, but it really baffled me:
Consider the BFS algorithm. Given the digraph G = (V, E) and the initial vertex s ∈ V, this algorithm computes for each vertex u ∈ V the value d [u], which is the length (number of edges) on the shortest path from s to u. The goal of this problem is to modify the BFS class algorithm to compute the number of shortest paths from s to each vertex G.
This can be done in two steps:
(a) Start standard BFS on G first, starting at s. Explain how to use the result of this BFS to create a new digraph G2 = (V 2, E 2), where V 2 ⊆ V and E2 ⊆ E such that every path in G2 starting at s is the shortest path in G starting at s , and conversely, every shortest path in G starting with s is a path in G2.
(b) Explain how to take the result of part (a) to calculate, for each vertex u ∈ V, the value n [u], which is the number of paths in G2 from s to u. (Hint: this can be done with a BFS modification.) Both of your algorithms should run in O (V + E).
For part a, I'm not really sure how to use the results from BFS to create a new digraph. I don't understand how / how it should be formed. Am I using the nodes that have been visited to form a new graph? All nodes are visited when doing BFS, how should I generate another schedule.
source to share
The issue (a)
can be resolved by running BFS normally, but for every edge (u, v)
you find when executing it, if shortest-path(u)+1 <= shortest-path(v)
(regardless of whether it v
has already been visited), then a (u, v)
directed edge in G2
.
Also, when doing this, in order to decide (b)
, you must increase n[v] += n[u]
. In the beginning n[u] = 0
for everyone except s
where n[s] = 1
.
Here's an example Python implementation:
from collections import deque
def bfs(G, s):
shortest = [float('+Inf')]*len(G)
count = [0]*len(G)
shortest[s] = 0
count[s] = 1
Q = deque([s])
while Q:
u = Q.popleft()
for v in G[u]:
if not count[v]:
Q.append(v)
if shortest[u]+1 <= shortest[v]:
shortest[v] = shortest[u]+1
count[v] += count[u]
return count
G = [
[1, 2, 3],
[4],
[4],
[4],
[]
]
print bfs(G, 0)
source to share