algorithm - 来自单个源顶点的最亮路径数

Question

假设我有一个具有正权或负权重的有向加权图（没有零或负权重循环）。该图是 Bellman-Ford 分析的，这意味着每个顶点都保存从源顶点到它的最轻路径的数据，以及它在最轻路径中的前身。存储从源到每个顶点的不同最短路径数量的最有效方法是什么？如果可能，我愿意在线性时间内完成 - O(V+E)。

Answer 1

如果你也没有负面边缘，你可以非常有效地做到这一点。

让到节点的最短路径v表示为D(v)

按距离对顶点进行排序 - O(VlogV)

表示P(v)- 从源到 的路径数v。
现在，您可以使用 DP 来解决这种关系（从头到尾）：

P(source) = 1
P(v) = sum { P(u) | (u,v) is an edge and D(u) + w(u,v) = D(v) }

算法的复杂度是O(VlogV + E)

正确性证明：通过归纳（准则）：
源的基本子句，只有一条路径（空路径）。
让我们假设 P(v) 对于每一个v这样的都是正确的D(v) < D(u)。

对于以 结束的每条最短路径u，它必须经过这样的顶点之一D(v) < D(u)。给定一条最短路径source->...->v->u，该路径被计算在内P(v)。此外，它不计入任何其他P(v')，因此它只计入 一次sum { P(u) | (u,v) is an edge and D(u) + w(u,v) = D(v) }。
此外，对于任何不是最短路径的路径，从归纳假设来看，它不计入任何v这样的D(v)<D(u)，所以路径必须在最后一步生成，但限制(u,v) is an edge and D(u) + w(u,v) = D(v)是阻止它，所以我们不计入任何非-最短路径。
量子点