如何使用networkx查找加權圖中的最短路徑？

Question

我使用Python 2.7 Enthought distribution中的networkx包來計算海港網絡之間的最短路徑。使用dijkstra_path_length可以很好地計算距離，但是我也需要知道使用dijkstra_path時發現了什麼路線（作爲一個例外，我認爲如果我先計算路徑，那麼運行速度應該更快，然後計算路徑的長度而不是在相同的數據上運行Dijkstra算法兩次）。但路徑功能失敗，說list indices must be integers, not str。

下面是產生錯誤的代碼。誰能告訴我我做錯了什麼？

import networkx as nx 

# Create graph 
network_graph = nx.Graph() 
f_routes = open('routes-list.txt', 'rb') 
# Assign list items to variables 
for line in f_routes: 
    route_list = line.split(",") 
    orig = route_list[0] 
    dest = route_list[1] 
    distance = float(route_list[2]) 
    # Add route as an edge to the graph 
    network_graph.add_edge(orig, dest, distance=(distance)) 

# Loop through all destination and origin pairs 
for destination in network_graph: 
    for origin in network_graph: 
     # This line works 
     length = nx.dijkstra_path_length(network_graph, origin, destination, "distance") 
     # This line fails 
     path = nx.dijkstra_path(network_graph, origin, destination, "distance") 

我在回溯中獲得以下內容。

Traceback (most recent call last): 
    File "C:\Users\jamie.bull\workspace\Shipping\src\shortest_path.py", line 67, in <module> 
    path = nx.dijkstra_path(network_graph, origin, destination, "distance") 
    File "C:\Enthought\Python27\lib\site-packages\networkx\algorithms\shortest_paths\weighted.py", line 74, in dijkstra_path 
    return path[target] 
TypeError: list indices must be integers, not str 

Answer 1

做實驗了一下，似乎nx.dijkstra_path提出了一個誤導性的異常，當出發地和目的地節點是相同的：

>>> import networkx as nx 
>>> g = nx.Graph() 
>>> g.add_edge('a', 'b', distance=0.3) 
>>> g.add_edge('a', 'c', distance=0.7) 
>>> nx.dijkstra_path_length(g, 'b', 'c', 'distance') 
1.0 
>>> nx.dijkstra_path(g, 'b', 'c', 'distance') 
['b', 'a', 'c'] 
>>> nx.dijkstra_path_length(g, 'b', 'b', 'distance') 
0 
>>> nx.dijkstra_path(g, 'b', 'b', 'distance') 
Traceback (most recent call last): 
    File "<pyshell#7>", line 1, in <module> 
    nx.dijkstra_path(g, 'b', 'b', 'distance') 
    File "C:\Users\barberm\AppData\Roaming\Python\Python27\site-packages\networkx\algorithms\shortest_paths\weighted.py", line 74, in dijkstra_path 
    return path[target] 
TypeError: list indices must be integers, not str 

所以只是做一個明確的測試是否destination和origin是相同的，並在它們分開時分開處理。