Wie finde ich den kürzesten Pfad in einer gewichteten Grafik mit networkx?

Question

Ich verwende das networkx Paket in Python 2.7 Enthought distribution, um kürzeste Wege zwischen einem Netzwerk von Seehäfen zu berechnen. Es funktioniert gut, um die Entfernung mit dijkstra_path_length zu berechnen, aber ich muss auch wissen, welche Route es mit gefunden hat (nebenbei, ich denke, es sollte schneller laufen, wenn ich den Pfad zuerst berechnen, dann berechnen Sie die Länge aus dem Pfad anstatt den Dijkstra-Algorithmus zweimal mit denselben Daten auszuführen. Die Pfadfunktion schlägt jedoch fehl und sagt list indices must be integers, not str.

Hier ist der Code, der den Fehler erzeugt. Kann mir jemand sagen, was ich falsch mache?

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") 

Ich bekomme das folgende im Traceback.

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

ein wenig Experimentieren, scheint es, dass nx.dijkstra_path eine irreführende Ausnahme auslöst, wenn die Ursprungs- und Zielknoten gleich sind:

>>> 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 

Also nur einen expliziten Test, ob destination und origin gleich sind, und behandeln sie getrennt, wenn sie sind.