algorithm - 查找从源到有向图中所有顶点的所有最短路径

Question

我们得到了一个具有正边权重的有向图 G（可能带有循环），并且还给出了从源 sD[v]到每个顶点的最小距离v（D 是这样的数组）。N[v] = number问题是在线性时间内找到长度D[v]从 s 到 v的路径数组。

现在这是一个我一直在努力解决的家庭作业问题。我正在按照以下想法工作：我试图通过适当地选择 G 的非循环子图来消除循环，然后尝试在子图中找到从 s 到 v 的最短路径。

但是我无法明确地弄清楚要做什么，所以我会很感激任何帮助，比如关于做什么的定性想法。

Answer 1

您可以在此处使用动态编程D[u] + w(u,v) = D[v]方法，并在执行过程中填写路径数，例如：

N = [0,...,0]
N[s] = 1 //empty path
For each vertex v, in *ascending* order of `D[v]`:
   for each edge (u,v) such that D[u] < D[v]:
       if D[u] + w(u,v) = D[v]: //just found new shortest paths, using (u,v)!
           N[v] += N[u]

复杂性是O(VlogV + E)，假设图不是稀疏的，O(E)占主导地位。

---

解释：

如果有一条从 到 的最短路径v0->v1->...->v_(k-1)->v_k，那么就是从v0到v_k的v0->...->v_(k-1)最短路径v0，v_k-1因此 - 在迭代时v_k-N[v_(k-1)]已经完全计算（请记住，所有边都有正权重，D[V_k-1] < D[v_k]并且我们正在通过增加 的值进行迭代D[v]）。
因此，路径v0->...->v_(k-1)被计入此时的数量N[V_(k-1)]。
由于v0->...->v_(k-1)-v_k是最短路径 - 这意味着D[v_(k-1)] + w(v_k-1,v_k) = D[v_k]- 因此条件成立，我们将把这条路径的计数添加到N[v_k].

请注意，该算法的证明基本上是归纳，它将更正式地遵循此解释中的指导方针。