寻找两个节点之间所有路径的快速算法

Question

我刚开始学习Python编程，想找一个算法，能快速找到一个大图中从起始节点到结束节点的所有路径。这个图大概有1000个节点和10000条边。实际上，从起始节点到结束节点的路径数量很少，十条以内。为了让问题更容易理解，可以想象一个社交网络——如果我有1000个朋友，想知道我高中最好的朋友和我大学室友之间有多少种连接方式，我并不关心我高中最好的朋友和我所有200个高中朋友的关系，因为这些关系并不会通向我的室友。我希望用这段Python代码快速找到这两个朋友之间的路径，并去掉周围那些“杂音”。

我尝试过很多代码示例，这些示例在小而简单的图上运行得很好。但是，当我把它们应用到我的大图分析时，它们都太慢了，没法用。

你们有没有什么建议的方法可以尝试（比如在networkx中已经创建好的东西，或者关于使用栈和递归的信息等等），或者可以实现的代码示例，甚至是其他编程语言的解决方案？请记住，我还是个Python新手。

Answer 1

我个人建议使用图数据库来处理这个问题。比如Neo4j或者Rexter这两个。

如果你想用Python来访问这些数据库，有几个库可以选择：

• http://bulbflow.com/overview/
• http://py2neo.org/

虽然现在写一个快速且可扩展的Python版本并不是不可能，但据我所知，目前还没有这样的版本。

Answer 2

也许你想要找出两个节点之间所有简单的路径（没有重复节点的路径）？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]