計算圖中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。效率部分取決於如何檢查訪問節點，以及如何查詢給定節點的相鄰節點。廣度優先搜索始終保證提供最佳距離，但是如果您的數據庫中有很多節點（如十億/百萬），則此實現可能會造成問題。我希望這給出了這個想法。