algorithm - 总最短路径的 BFS 修改

Question

我被分配了以下问题，但它真的让我感到困惑:

Consider the BFS algorithm. Given a digraph G = (V, E) and a starting 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 objective of this problem is to modify the BFS algorithm of class to compute the number of shortest paths from s to each vertex of G.

This can be done in two steps:

(a) First run the standard BFS on G, starting from s. Explain how to use the result of this BFS to produce a new digraph G2 = (V 2,E2), where V 2 ⊆ V and E2 ⊆ E, such that every path in G2 that starts at s, is a shortest path in G starting from s, and conversely, every shortest path in G starting from s is a path in G2.

(b) Explain how to take the result of part (a) to compute for each vertex u ∈ V , a quantity n[u], which is the number of paths in G2 from s to u. (Hint: This can be done by a modification of BFS.) Both of your algorithms should run in O(V + E) time.

对于 a 部分，我不太确定如何使用 BFS 的结果来生成新的有向图。我不明白它应该如何/以什么方式形成。我是否使用访问过的节点来形成新图？做 BFS 时访问所有节点，我应该如何形成不同的图。

Answer 1

问题(a)可以通过正常运行 BFS 来解决，但对于每条边 (u, v)你在做的时候发现，如果shortest-path(u)+1 <= shortest-path(v) (不管 v 是否已经被访问过)然后 (u, v)是 G2 中的有向边.

另外，一边做一边解决(b)你应该增加n[v] += n[u] .一开始，n[u] = 0对于除s以外的所有人, 其中n[s] = 1 .

这是一个 Python 实现示例:

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)