如何让NetworkX在多重图路径规划中返回边序列而非节点序列？

针对你遇到的NetworkX多重图路径仅返回节点序列、无法区分边的问题，有两种高效的解决方案：

方法1：使用edge_dijkstra直接返回边序列 #

NetworkX提供了edge_dijkstra函数，专门用于返回包含边标识（key）的路径序列，完美适配多重图场景。它会直接返回形如(u, v, key)的三元组，明确指定路径使用的边。

示例代码：

import networkx as nx

edges = [
    (0,1,0, {'cost': 3}),
    (1,2,0, {'cost': 5}),
    (1,2,1, {'cost': 10}),
]

G = nx.MultiGraph()
G.add_edges_from(edges)

# 获取边序列路径
edge_path = list(nx.edge_dijkstra(G, source=0, target=2, weight='cost'))
# 计算总代价
total_cost = sum(G[u][v][k]['cost'] for u, v, k in edge_path)

print(total_cost)  # 8
print(edge_path)   # [(0, 1, 0), (1, 2, 0)]

方法2：通过前驱字典回溯边信息 #

如果需要使用其他无对应edge_*版本的路径算法，可以通过获取前驱节点字典，结合节点距离差回溯找到对应边：

import networkx as nx

edges = [
    (0,1,0, {'cost': 3}),
    (1,2,0, {'cost': 5}),
    (1,2,1, {'cost': 10}),
]

G = nx.MultiGraph()
G.add_edges_from(edges)

# 获取前驱节点字典和各节点到源点的距离
predecessors, distances = nx.dijkstra_predecessors_and_distance(G, source=0, weight='cost')
target = 2

edge_path = []
current = target
# 从目标节点回溯到源节点
while current != 0:
    prev_node = predecessors[current]
    # 找到符合距离差的边（最短路径的边权重等于两节点距离差）
    for edge_key, attrs in G[prev_node][current].items():
        if distances[current] - distances[prev_node] == attrs['cost']:
            edge_path.append((prev_node, current, edge_key))
            break
    current = prev_node

# 反转得到源到目标的顺序
edge_path.reverse()

print(distances[target])  # 8
print(edge_path)          # [(0, 1, 0), (1, 2, 0)]

说明 #

• edge_dijkstra是最简洁的方案，优先使用；
• 回溯法适用于更多路径算法场景，核心逻辑是利用最短路径中边权重等于节点距离差的特性，精准匹配对应边。

内容的提问来源于stack exchange，提问作者olamarre