Python 计算图中两个节点之间的距离
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3601180/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
calculate distance between 2 nodes in a graph
提问by nababa
I have directed graph stored in the following format in the database {STARTNODE, ENDNODE}. Therefore, {5,3} means there is an arrow from node 5 to node 3.
我在数据库 {STARTNODE, ENDNODE} 中以以下格式存储了有向图。因此，{5,3} 表示存在从节点 5 到节点 3 的箭头。
Now I need to calculate the distance between two random nodes. What is the most efficient way? By the way, the graph is has loops.
现在我需要计算两个随机节点之间的距离。最有效的方法是什么？顺便说一下，图是有循环的。
Thanks a lot!
非常感谢！
采纳答案by razpeitia
As you can see here
正如你在这里看到的
If you have unweighted edges you can use BFS
如果您有未加权的边缘，您可以使用BFS
If you have non-negative edges you can use Dijkstra
如果您有非负边缘，则可以使用Dijkstra
If you have negative or positive edges you most use Bellman-Ford
如果您有负边或正边，您最常使用Bellman-Ford
回答by Sjoerd
回答by unutbu
If by distance we mean the minimum number of hops, then you could use Guido van Rossum's find_shortest_pathfunction:
如果距离是指最小跳数，那么您可以使用 Guido van Rossum 的find_shortest_path函数：
def find_shortest_path(graph, start, end, path=[]):
"""
__source__='https://www.python.org/doc/essays/graphs/'
__author__='Guido van Rossum'
"""
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
shortest = None
for node in graph[start]:
if node not in path:
newpath = find_shortest_path(graph, node, end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
if __name__=='__main__':
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}
print(find_shortest_path(graph,'A','D'))
# ['A', 'B', 'D']
print(len(find_shortest_path(graph,'A','D')))
# 3
回答by Tamás
If you are really looking for the most efficient way, then the solution is to implement breadth first searchin C and then call the implementation from the Python layer. (Of course this applies only if the edges are unweighted; weighted edges require Dijkstra's algorithmif the weights are non-negative, or the Bellman-Ford algorithmif weights can be negative).
如果你真的在寻找最有效的方式，那么解决方案是在 C 中实现广度优先搜索，然后从 Python 层调用实现。（当然，这仅适用于边缘未加权的情况；如果权重为非负，加权边缘需要Dijkstra 算法，或者如果权重可以为负，则需要Bellman-Ford 算法）。
Incidentally, the igraph libraryimplements all these algorithms in C, so you might want to try that. If you prefer a pure Python-based solution (which is easier to install than igraph), try the NetworkXpackage.
顺便说一下，igraph 库在 C 中实现了所有这些算法，因此您可能想尝试一下。如果您更喜欢纯基于 Python 的解决方案（比igraph更易于安装），请尝试使用NetworkX包。
回答by Gant
Given that the distance is the number of hops, and is optimal (shortest path.) You may keep track of visited nodes and current reachable nodes using Python's list/set. Starts from the first node and then keep hopping from the current set of nodes until you reach the target.
鉴于距离是跳数，并且是最佳的（最短路径）。您可以使用 Python 的列表/集合跟踪访问过的节点和当前可到达的节点。从第一个节点开始，然后从当前节点集继续跳跃，直到到达目标。
For example, given this graph:
例如，给定这个图：
[hop 0]
visited: {}
current: {A}
[hop 1]
visited: {A}
current: {B, C, J}
[hop 2]
visited: {A, B, C, J}
current: {D, E, F, G, H}
[hop 3]
visited: {A, B, C, D, E, F, G, H, J}
current: {K} // destination is reachable within 3 hops
The point of visited-node list is to prevent visiting the visited nodes, resulting in a loop. And to get shortest distance, it's no use to make a revisit as it always makes the distance of resulting path longer.
访问节点列表的目的是防止访问访问节点，导致循环。为了获得最短距离，重新访问是没有用的，因为它总是会使结果路径的距离更长。
This is a simple implementation of Breadth-first search. The efficiency partly depends on how to check visited nodes, and how to query adjacent nodes of given node. The Breadth-first search always guarantee to give optimal distance but this implementation could create a problem if you have lots of node, say billion/million, in your database. I hope this gives the idea.
这是广度优先搜索的简单实现。效率部分取决于如何检查访问过的节点，以及如何查询给定节点的相邻节点。广度优先搜索始终保证提供最佳距离，但如果您的数据库中有大量节点，例如十亿/百万，这种实现可能会产生问题。我希望这给出了想法。
