全部配对图表上的所有路径
这可能是一个没有最佳解决方案的问题。假设我有一个有向图，不知道它是否有循环（循环检测将是这个问题的方面之一）。给定一组顶点（可能是数百万个顶点），我需要计算给定图的所有唯一对之间的所有不同路径（没有重复顶点的路径）。我该如何应对这种情况？
让我们看一下执行此操作的强力方法：
从图中计算所有可能的对。
对于每对图，使用 DFS 获取从 Source 到 目的地。
- 假设这些对在哈希表中表示，将路径计数作为该对的值。
- 对其余的对重复此操作。
人们能指出这可能会出现哪些问题吗？让我们以这种方式思考这个问题，找到地球上所有城市之间的所有不同路径的计算挑战是什么？如果有人试图解决这个问题，会从哪里开始？
编辑：提出的一些算法在 O(n!) 阶乘时间内产生结果。对于处理资源有限的单台机器来说，这有点令人畏惧的计算。有谁知道映射缩减技术可以将图遍历问题分解为更小的块？
This is possibly a problem with possibly no optimal solution. Suppose I have a directed graph, have no clue whether it has any cycles or not(cycle detection will be one of the aspects of this problem). Given a set of vertices(possibly millions of vertices) I need to count all the distinct paths(paths with no duplicate vertices) between all the unique pairs of the given graph. How would I go about tackling this situation?
Lets look at a brute-force way to do this:
Compute all possible pairs from the graph.
For each pair of the graph use DFS to get all the paths from Source to
Destination.- Assuming the pairs are represented in a hash table, put the path count as the value against this pair.
- Repeat for the rest of the pairs.
Can people point out what are some of the things that can go wrong with this? Lets think of the problem in this manner, what are the computational challenges of finding all the distinct paths between all the cities of the planet and if one would even attempt to solve this problem, where would one start?
Edit: Some of the algorithms presented produce results in O(n!) factorial time. This is somewhat of a daunting computation for a single machine with limited resources to handle. Does anyone know of map-reduce techniques to break down the problem of graph traversal into smaller chunks?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
获得粗略近似路径的 Floyd-Warshall 概括是这样的：
这里有一个关于如何扩展它的非常粗略的想法。免责声明 - 这不是具体的 - 它非常曲折，但希望它能提供更多帮助，而不是造成混乱。它有助于理解算法的工作原理。它从图的邻接矩阵开始。在每次迭代 k 中，我们说从 i 到 j 的路径数等于先前迭代中从 i 到 j 的路径数加上从 i 通过 k 到 j 的路径数。
因此，将图分解为 n 个大小为 kxk 的任意子邻接矩阵，对每个矩阵进行上面的计算。现在您有了路径的数量，并通过在组合矩阵上重新计算上述部分来开始组合子矩阵。即，我们只需要在重新组合时重新计算 k 的 n/2 个值。我发现这个，看起来像一个类似的方向 http://theory.stanford。 edu/~oldham/publications/generalized/asgsp.pdf。
The Floyd-Warshall generalization that gets a rough approximation of paths is this:
Here is a very rough idea on how to scale this. Disclaimer - This isn't concrete -it's very hand wavy, but hopefully it helps more than confuses. It helps to understand how the algorithm works. It starts on an adjacency matrix of the graph. In each iteration k, we're saying the number of paths from i to j is equal to the number of paths in prior iterations from i to j plus the number of paths from i to j via k.
Thus Break the graph in to n arbitrary sub-adjacency matricies of size k x k, compute above on each of them. Now you have the number of paths and start combining submatricies by recomputing part of the above on the combined matrix. I.e, we only need to recompute n/2 values for k when recombining. I found this, which looks like a similar direction http://theory.stanford.edu/~oldham/publications/generalized/asgsp.pdf.
你有没有想过这样的路径可以存在多少条？
在这样一个具有 V 个顶点的图中，大约有 V^2 个不同的对。让我们想象一个最坏的情况，您有一个完整的图（每对之间都存在边）。路径可以具有 1 条边和 V-1 条边之间的任意位置，因为路径中不允许有重复的顶点。
每对顶点之间：
鉴于此，我们知道最多有 V^2*sum{i=1 -> V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(Vk-1)) 具有 V 个顶点的图的总路径。
因此路径总数为 P(V) = V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(Vk-1)) = V^2*sum{i=1 -> V-1}(O(V^V)) = O(V^3*V^V) = O(V!)。
现在想象一个理想的世界，您可以在恒定的时间内计算每条路径。您的算法将需要 O(1*V!) = O(V!) 时间来运行，这是不切实际的。
可能有一种算法可以对路径进行计数而不用枚举它们，从而获得更有效的算法。
Have you thought how many such paths can exist?
In such a graph with V vertices, you have about V^2 different pairs. Let's imagine a worst case scenario where you have a full graph (one where edges exist between every pair). Paths can have anywhere between 1 edge and V-1 edges, because you do not allow duplicate vertices in a path.
Between each pair of vertices:
Given that, we know that there are at most V^2*sum{i=1 -> V-1}(prod{k=1 -> i-1}(V-k-1)) total paths for a graph with V vertices.
The total number of paths is therefore 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!).
Now imagine an ideal world where you can compute each path in constant time. Your algorithm would take O(1*V!) = O(V!) time to run, which is impratical.
There might be an algorithm that can count the paths without enumerating them, and thus get a more efficient algorithm.
此页面描述了一种 DFS 方法打印任意两个顶点之间的所有非循环路径——它还包括 java 代码。您可以修改它以查找所有顶点对的所有此类路径，但这不是计数所有顶点之间所有路径的最有效方法。
This SO page describes a DFS method for printing all non-cyclic paths between any two vertices--it also includes java code. You can modify it to find all such paths for all pairs of of vertices, but it's not the most efficient way of counting all paths between all vertices.