如何使用networkx在加权图中找到最短路径? [英] How to find shortest path in a weighted graph using networkx?

问题描述

我正在使用Python 2.7 Enthought distribution中的networkx程序包来计算海港网络之间的最短路径.使用dijkstra_path_length计算距离可以正常工作，但是我还需要知道使用dijkstra_path找到的路线(顺便说一句，如果我先计算路径然后计算路径，我认为运行起来应该会更快一些)路径的长度，而不是对同一数据两次运行Dijkstra的算法).但是路径功能失败，提示list indices must be integers, not str.

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

推荐答案

进行一点实验，当源节点和目标节点相同时，nx.dijkstra_path似乎引发了误导性异常:

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

因此，只需明确测试destination和origin是否相同，并分别处理它们即可.

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

这篇关于如何使用networkx在加权图中找到最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！