如何使用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

- Jamie Bull

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是否相同，并在它们相同时单独处理。

- Michael J. Barber

---

一个完全的新手问题：在这种情况下，“权重”或“距离”，是低的更容易还是反过来？更高的权重使路径上的边更可取吗？ - Jason