BFS修改以求解总最短路径问题

Question

我得到了以下问题作为任务，但它真的让我感到困惑：

考虑BFS算法。给定有向图G=(V,E)和起始点s∈V，该算法计算对于每个顶点u∈V的值d[u]，其中d[u]是从s到u的最短路径长度（边数）。这个问题的目标是修改BFS类算法，以计算从s到G中每个顶点的最短路径数量。

这可以分为两步完成：

(a)首先在G上运行标准BFS，从s开始。解释如何使用此BFS结果生成一个新的有向图G2 = (V2,E2)，其中V2⊆V且E2⊆E，使得G2中所有从s开始的路径都是G中从s开始的最短路径，反之亦然，即G中从s开始的每条最短路径都是G2中的路径。

(b)解释如何利用第(a)部分的结果来计算每个顶点u∈V的数量n[u]，其中n[u]是从s到u的G2路径数量。（提示：可以通过BFS的修改来完成这一点。）你的两个算法应该在O(V + E)时间内运行。

对于第(a)部分，我不太确定如何利用BFS结果生成新的有向图。我不理解应该以怎样的方式形成它。我应该使用访问的节点来形成一个新的图吗？当进行BFS时，所有节点都被访问，我该如何形成不同的图。

- Jmrapp

---

这个问题可能更适合在 math.stackexchange 上提问。 - Degustaf

Answer 1

问题 (a) 可以通过正常运行BFS来解决，但是在执行过程中，对于每个发现的边 (u, v)，如果shortest-path(u)+1 <= shortest-path(v)（不管 v 是否已经访问过），那么 (u, v) 就是 G2 中的有向边。

此外，在执行过程中，为解决 (b) 问题，应增加 n[v] += n[u]。一开始，除了 s 外，每个节点的 n[u] 均为零，其中 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)       

- Juan Lopes