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)正在阻止它，所以我们不计算任何非最短路径。
QED