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

Question

我在数据库里存储了一个有向图，格式是 {起始节点, 结束节点}。比如说，{5,3} 就表示从节点 5 指向节点 3，有一条箭头。

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

非常感谢！

Answer 1

在这里，距离是指跳跃的次数，而我们要找的是最短的路径。你可以用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

记录已经访问过的节点是为了避免重复访问同一个节点，这样会导致死循环。而且为了找到最短的距离，重新访问已经走过的节点是没有意义的，因为这样只会让路径变得更长。

这其实是广度优先搜索的一种简单实现。它的效率部分取决于你如何检查已经访问的节点，以及如何查询某个节点的相邻节点。广度优先搜索总是能保证找到最优的距离，但如果你的数据库中有很多节点，比如亿级或百万级的节点，这种实现可能会出现问题。希望这些能让你明白这个概念。

Answer 2

如果我们说的“距离”是指最少的跳数，那么你可以使用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

Answer 3

正如你在这里看到的，

如果你的图里边的边没有权重（也就是没有数值），你可以使用广度优先搜索（BFS）。

如果你的边的权重是非负数（也就是边的数值都是零或正数），你可以使用Dijkstra算法。

如果你的边的权重有负数或正数，那你最好使用Bellman-Ford算法。