python - 修改 Dijkstra 以进行计数

Question

我在某处读到，可以修改 Dijkstra 算法来计算两个顶点之间的最短路径数。如果这是我对 Dijkstra 算法的实现，我该如何修改它来计数？

def dijkstra(G, s, t):
    D, P = {}, {}
    Q = {v: float('inf') for v in G}
    Q[s] = 0

    for v in Q:
        D[v] = Q[v]
        if v == t: break

        for w in G[v]:
            if D[v] + G[v][w] < Q[w]:
                P[w] = v
                Q[w] = D[v] + G[v][w]
    return D, P

是否像在 D[v] + G[v][w] = Q[w] 时递增计数器并在小于 Q[w 时重置计数器一样简单？ ]?

Answer 1

Is it as simple as incrementing a counter when D[v] + G[v][w] = Q[w] and resetting the counter when it's less than Q[w]?

不完全是。如果 D[v] + G[v][w] == G[w]，这并不意味着您找到了一个到 w 的临时最短路径.毕竟，到 v 可能有多条最短路径，每条路径都会为您提供一条到 w 的临时最短路径。您需要将 v 的计数器值添加到 w 的计数器。此外，如果您重置 w 的计数器，您会将其重置为 v 的计数器值，而不是 0。