两个节点之间的所有路径的非常快速算法

Question

两个节点之间的所有路径的非常快速算法

10

我对Python编程非常陌生，正在寻找一种算法，能够快速查找一个非常大的图中起点和终点之间的所有路径。比如说，一个有大约1000个节点和10000条边的图。实际上，从起点到终点存在的路径数量很少，不超过10条。为了更好地解释问题，可以考虑社交网络——如果我有1000个朋友，想知道我高中最好的朋友和我大学室友的联系方式，那么我并不关心我的高中朋友与我200个高中朋友的联系方式，因为这些路径永远不会通向我的室友。我想用Python代码快速筛选出两个朋友之间存在的路径，并消除围绕这两个节点的所有“噪声”。

我尝试了许多小型简单图的代码示例，它们都运行良好。但是，当我尝试将它们应用于我的大型图分析时，它们都需要太长时间，不太实用。

您们是否有任何建议或方法可以探究（例如，在networkx中已经创建了某些方法，或者使用堆栈与递归等），或者可以实现的代码示例，甚至是在Python以外的其他路线？请记住，我是一个Python新手。

- Garen Pledge

将此帖子中的一个解决方案翻译成Python：https://dev59.com/questions/1XVD5IYBdhLWcg3wL4iM - Adrián

还有这个：https://dev59.com/iGox5IYBdhLWcg3w3YD- - Adrián

1

挑战在于知道你是否已经找到了它们。我认为这是不可能的，除非检查大量节点。算法不能忽略你的200个朋友，因为它无法知道（除非检查他们及其进一步的朋友），他们是否与你的室友相连。事实上，确定是否存在通过这些朋友的路径不正是运行搜索的全部意义吗？ - Blckknght

Adrian - 感谢提供的资源！我一定会去查看的。Blckknght - 说得好 - 我遇到了与你看到的相同的挑战。我考虑的一件事是，我希望该过程查看所有节点，但仅输出从一个节点到结束的路径。我目前想到的是找到“1跳”和“2跳”等节点...但为了使算法快速运行，我需要使用哈希表/查找数组而不是队列（到目前为止我已经使用了队列）- 是否有人看到这方面存在问题？ - Garen Pledge

2个回答

1

我个人建议使用图形数据库来处理这个问题。Neo4j或Rexter是比较好的选择。

在Python中访问这些数据库时，有一些可用的库：

尽管编写一个快速/可扩展的Python版本并非不可能，但据我所知目前还没有这样的版本。

- Wolph

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aric · Accepted Answer

也许你想要两个节点之间的所有简单路径（没有重复节点）？NetworkX有一个基于深度优先搜索的函数可以实现这一点。请参见http://networkx.github.com/documentation/development/reference/generated/networkx.algorithms.simple_paths.all_simple_paths.html。从那里的示例可以看出，简单路径的数量可能很大。

>>> import networkx as nx
>>> G = nx.complete_graph(4)
>>> for path in nx.all_simple_paths(G, source=0, target=3):
...     print(path)
...
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 1, 3]
[0, 2, 3]
[0, 3]