所有点对间的最短路径问题

Question

这可能是一个没有最优解的问题。假设我有一个有向图，不知道它是否有任何环路（检测环路将是这个问题的一个方面）。给定一组顶点（可能有数百万个顶点），我需要计算给定图中所有唯一对之间的所有不同路径（具有不重复顶点的路径）的数量。如何解决这种情况？

让我们看看一种暴力的方法来解决这个问题：

- 计算出图中所有可能的配对。 - 对于图中的每一对，使用DFS获取源到目标的所有路径。 - 假设这些配对在哈希表中表示，将路径计数作为该配对的值。 - 重复处理其余的配对。

人们能指出这种方法可能会出现什么问题吗？让我们从这个角度思考问题，找到地球上所有城市之间所有不同路径的计算难题，并且如果有人尝试解决这个问题，应该从哪里开始？

编辑：其中一些算法产生O(n!)阶乘时间的结果。对于资源有限的单台机器来说，这是一项令人望而却步的计算。有人知道用MapReduce技术将图遍历问题分解成更小的块吗？

- sc_ray

---

当您发现循环时，您想如何处理它们？比如给出一个图形 {(A,B), (B,C), (C,A), (C,D)}。在 A 和 D 之间有无数个不同的路径：ABCD、ABCABCD、ABCABCABCD、ABCABCABCABCD... 任何循环图都有无数个不同的路径连接其所有节点对。 - R. Martinho Fernandes

假设您在第一次遍历时标记了顶点。在这种情况下，唯一的不同路径是ABCD。您需要按照A->B->C->D的顺序进行遍历。任何重访顶点的遍历都将被丢弃。 - sc_ray

@sc_ray 在你的问题中加入这个限制会得到更好的答案。 "不同路径" 和 "没有重复顶点的路径" 不是同一回事。 - R. Martinho Fernandes

@Martinho Fernandes - 理解了。已更新帖子。 - sc_ray

重复？- https://dev59.com/PXI-5IYBdhLWcg3w18d3 - dfb

Answer 1

弗洛伊德-沃舍尔(Floyd-Warshall)算法是一个大概估计路径的通用算法，其实现如下：

 procedure FloydWarshall ()
    for k := 1 to n
       for i := 1 to n
          for j := 1 to n
             path[i][j] = path[i][j] + path[i][k]*path[k][j] 

这里有一个非常粗略的想法，可以用来扩展它。免责声明-这不是具体的-非常模糊，但希望它能帮助你更好地理解。了解算法如何工作很有帮助。它从图的邻接矩阵开始。在每个迭代k中，我们说从i到j的路径数等于先前迭代从i到j的路径数加上通过k从i到j的路径数。

因此，将图分为n个任意大小为k x k的子邻接矩阵，在每个矩阵上计算上述内容。现在您拥有路径的数量，并通过重新计算以上部分来组合子矩阵。也就是说，当重新组合时，我们只需要重新计算k的n/2个值。我找到了这个链接，看起来是类似的方向：http://theory.stanford.edu/~oldham/publications/generalized/asgsp.pdf。

- dfb

---

这不取决于执行的顺序吗？例如，如果首先对i k和k j进行正确的迭代运行，那么从i到j的路径是否通过k存在？ - Marcel

随着k的增加，我们构建越来越长的路径。在哪个方向上构建这些长路径并不重要。 - Marcel

Answer 2

你曾经想过这样的路径有多少条吗？

在具有V个顶点的图中，你大约有V^2不同的对。让我们想象一个最坏的情况，即你拥有一个完整的图（其中每对之间都存在边缘）。路径可以有1个到V-1个边缘，因为路径中不允许重复的顶点。

在每对顶点之间：

1. 只有一条1个边缘的路径；
2. 有V-2条2个边缘的路径：使用任何不是起点或终点的中间顶点；
3. 有(V-2)(V-3)条3个边缘的路径：使用任意两个不同的中间顶点；
4. 有(V-2)(V-3)(V-4)条4个边缘的路径；
5. 有prod{k=1 -> n-1}(V-k-1)条n个边缘的路径。

鉴于此，我们知道对于具有V个顶点的图，最多有V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(V-k-1))种路径。

因此，总路径数为P(V) = V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(V-k-1)) = V^2*sum{i=1 -> V-1}(O(V^V)) = O(V^3*V^V) = O(V!)。

现在想象一个理想的世界，你可以在常数时间内计算每条路径。你的算法将需要O(1*V!) = O(V!)的时间来运行，这是不切实际的。

可能有一种算法可以计算路径而不枚举它们，从而获得更有效的算法。

- R. Martinho Fernandes

---

有人能告诉我如何将我的求和与乘积“数学化”吗？ - R. Martinho Fernandes

感谢分析。我以为它会像O(V!)一样非常耗时。我正在寻找解决这种规模问题的实用策略。 - sc_ray

直接的HTML应该可以工作：& Sigma;和& Pi;（&符号后面没有空格）。另请参阅XML和HTML字符实体引用列表。 - denis

Answer 3

这个SO页面描述了一种深度优先搜索方法，用于打印任意两个顶点之间的所有非循环路径--它还包括Java代码。您可以修改它以查找所有顶点对之间的所有这样的路径，但这不是计算所有顶点之间路径的最有效方法。

- oosterwal