How to find shortest path in a weighted graph usin

Question

I'm using the networkx package in Python 2.7 Enthought distribution to calculate shortest paths between a network of seaports. It's working fine to calculate the distance using dijkstra_path_length, but I also need to know what route it has found using dijkstra_path (as an aside, I think it should be faster to run if I calculate the path first, then calculate the length from the path rather than running Dijkstra's algorithm twice on the same data). However the path function is failing, saying list indices must be integers, not str.

Here's the code that produces the error. Can anyone tell me what I'm doing wrong?

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

I'm getting the following in the 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

Experimenting a bit, it appears that nx.dijkstra_path raises a misleading exception when the origin and destination nodes are the 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

So just make an explicit test whether destination and origin are the same, and handle it separately when they are.