Jak znaleźć najkrótszą ścieżkę na ważonym wykresie za pomocą networkx?

Question

Używam pakietu networkx w Python 2.7 Enthought distribution do obliczania najkrótszych ścieżek między siecią portów morskich. To działa dobrze, aby obliczyć odległość za pomocą dijkstra_path_length, ale muszę również wiedzieć, jaką drogę znalazł przy użyciu dijkstra_path (na marginesie, myślę, że powinno być szybciej, aby uruchomić, jeśli najpierw obliczyć ścieżkę, a następnie obliczyć długość ze ścieżki zamiast dwukrotnie uruchamiać algorytm Dijkstry na tych samych danych). Jednak funkcja ścieżki kończy się niepowodzeniem, mówiąc: list indices must be integers, not str.

Oto kod, który generuje błąd. Czy ktoś może mi powiedzieć, co robię źle?

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

Otrzymuję następujące informacje w 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

eksperymentowanie trochę, wydaje się, że nx.dijkstra_path podnosi mylący wyjątek, gdy pochodzenie i przeznaczenie węzły są takie same:

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

Więc po prostu zrobić wyraźną próbę czy destination i origin są takie same, i obchodzić się z nim osobno, gdy są.