计算图中2个节点之间的距离

Question

我在数据库{STARTNODE，ENDNODE}中存储了以下格式的有向图。因此，{5,3}意味着从节点5到节点3有一个箭头。

现在我需要计算两个随机节点之间的距离。什么是最有效的方法？顺便说一下，图形有循环。

非常感谢！

Answer 1

正如你可以see here

如果您有未加权的边缘你可以使用BFS

如果你有非负边缘您可以使用Dijkstra

如果你有你最常使用Bellman-Ford

Answer 2

Dijkstra's algorithm

Answer 3

如果距离我们的意思是跳的最小数量，那么你可以使用吉多·范罗苏姆的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 

Answer 4

如果你真的在寻找最有效的方式消极或积极的边缘，那么解决方案是实现breadth first search在C，然后调用从实施Python层。 （当然，这仅适用于边缘未加权的情况;如果权重非负，则加权边缘要求Dijkstra's algorithm，如果权重可以为负，则加权边缘要求Bellman-Ford algorithm）。

顺便提一下，igraph library在C中实现了所有这些算法，因此您可能需要尝试。如果您更喜欢纯粹的基于Python的解决方案（比igraph更容易安装），请尝试使用NetworkX软件包。

Answer 5

鉴于距离是跳数，并且是最优路径（最短路径）。您可以使用Python的列表/集跟踪访问节点和当前可到达节点。从第一个节点开始，然后继续从当前节点组跳跃，直到到达目标。

例如，给定该图表：

[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 

受访节点列表的点是为了防止访问访问节点，从而产生一个循环。为了获得最短的距离，重新进行重访是没有用的，因为它总是使得所得路径的距离更长。

这是一个简单的实现Breadth-first search。效率部分取决于如何检查访问节点，以及如何查询给定节点的相邻节点。广度优先搜索始终保证提供最佳距离，但是如果您的数据库中有很多节点（如十亿/百万），则此实现可能会造成问题。我希望这给出了这个想法。