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

Question

给定一个有向图 G（可能存在环）和正边权，同时给出了源点 s 到每个顶点 v 的最短距离 D[v]（用数组 D 表示）。问题是要在线性时间内找到从 s 到 v 长度为 D[v] 的路径数量 N[v]。

现在这是我一直以来苦苦思考的作业问题。我一直在按照以下思路进行：通过合适地选择 G 的无环子图来移除环，然后尝试在子图中寻找从 s 到 v 的最短路径。

但我无法明确地想出该如何做，所以非常感谢任何形式的帮助，例如关于该如何解决问题的定性建议。

- Urysohn Lemma

---

请注意，如果您添加了“简单路径”限制，您可以通过简单地发送D=[n,n,...,n]将哈密顿路径问题缩小到其中。这通常是一个很好的直觉，表明问题本身也是NPC，除非您在图形结构上错过了一些限制。 - amit

@amit，D[v] 是从 s 到 v 的最短路径距离，而不是任意距离（并且已给出）。 - Saeed Amiri

@SaeedAmiri 不确定我理解你的意思。已经给出了最短距离，您只需找出有多少条最短路径？ - amit

@amit，我猜是这样，因为我能看到它写着。 （似乎只是一个计数问题） - Saeed Amiri

@UrysohnLemma，你的D数组是否已经排序？ - Saeed Amiri

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到v_k存在最短路径v0->v1->...->v_(k-1)->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]中。

请注意，此算法的证明基本上将是归纳证明，将按照此解释的指导方针更加正式地进行。

- amit

---

虽然这是一个优雅的解决方案，但如果这是一个稀疏图，它不会是非线性的吗？我认为动态规划可能涉及其中，但需要一个严格线性的算法... - Urysohn Lemma

在寻找合适的子图等方面，难道没有类似的方法吗？（在解决问题这么长时间后，我希望涉及此方法的某些东西可以起作用） - Urysohn Lemma

@UrysohnLemma 我想不出有什么例外的情况，通常涉及查找子图的问题都是个难题（最小生成树是显然的例外），但我不知道这里是否也是如此。 - amit

我同意有不同的看法，但请在我的评论中准确表述。我说当你说线性时（单独，没有其他东西），你应该说是线性的原因是...，或者你可以说是线性的边数+顶点数，甚至伯克利讲座也说它是线性的E（并解释了为什么他们没有说它是线性的V）。 （我同意有分歧）。附言：我没有说你犯了错误，我是说根据我的理解，你的答案并不是那种期望的线性。 - Saeed Amiri

@Dukeling添加了一些解释。我不理解你的例子，如果你能更好地阐述它，我会尝试在答案中逐步添加一个示例。 - amit