所有对在图上的所有路径 [英] All pairs all paths on a graph

问题描述

这是可能与可能没有最优解的一个问题。假设我有一个有向图，不知道是否有任何循环或没有（周期检测将是这个问题的一个方面）。给定一组顶点（可能是数以百万计的顶点），我需要计算所有的所有独特的对给定的图形之间的不同的路径（没有重复的顶点路径）。我将如何去应对这种情况？

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.

对于每一对图形使用DFS让所有的路径，从源到 目的地。

For each pair of the graph use DFS to get all the paths from Source to Destination.

人能指出有哪些的东西，可以去错了吗？让我们觉得这种方式的问题，什么是发现地球上所有的城市之间，如果一个人甚至会试图解决这个问题，在这里总会有开始所有的不同的路径的计算挑战？

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?

编辑：一些算法presented产生的结果为O因子时间（n！）。这是有点一项艰巨的计算与有限的资源来处理一台机器。有谁知道的map-reduce方法来分解图的遍历的问题分解成更小的块？

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?

推荐答案

在弗洛伊德-沃肖尔推广，获取的路径粗略的估计是这样的：

The Floyd-Warshall generalization that gets a rough approximation of paths is this:

 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的数目。

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.

因此​​打破图形中到n任意子邻接尺寸kxk的基质中，计算上述对他们每个人。现在你有路径数，并开始通过组合矩阵上重新计算上述的一部分组合submatricies。也就是说，我们只需要重新组合时，重新计算N / 2的值对于k。我发现这一点，它看起来像一个类似的方向 HTTP：//theory.stanford。埃杜/〜奥尔德姆/出版/推广/ asgsp.pdf 。

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.

这篇关于所有对在图上的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！