寻找多个节点之间的最短路径（不仅仅是距离）

Question

我试图找到穿过图中指定节点的最短路径（A -> B -> C 而不仅仅是 A -> C）。目前，我的代码将 return 最短路径而不是通过所有指定的节点。

代码：

from networkx import DiGraph
from networkx.algorithms.shortest_paths import multi_source_dijkstra

graph = {'c1': {'c2': 4, 'L1': 3},
         'c2': {'c1': 4, 'c3': 3, 'L1': 2.5},
         'c3': {'c2': 3, 'L1': 2},
         'L1': {'c1': 3, 'c2': 2.5, 'c3': 2}}

# Build the graph
G = DiGraph()
G.add_weighted_edges_from(((source, target, weight)
                           for source, d in graph.items()
                           for target, weight in d.items()))

# Find shortest path (using Dijkstra algorithm)
#result = shortest_path(G, source='c1', target='c3', weight='weight')
result = multi_source_dijkstra(G, sources=['c2','c3'], target='L1')

print(result)
# result: (2, ['c3', 'L1'])

我正在使用的库和函数：https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path.html#networkx.algorithms.shortest_paths.weighted.multi_source_dijkstra_path

我注意到 networkx 有两个旅行商功能，但它们都不能 return 路径，只能距离，所以我认为我不能使用它们。

Answer 1

您应该多次调用 shortest_path，每个子路径调用一次。所以当请求是A->B->C时，求A到B的最短路径和B到C的最短路径，将两个结果拼接起来。

multi_source_dijkstra 做一些不同的事情：它找到从源节点之一到目标节点的路径。

寻找多个节点之间的最短路径（不仅仅是距离）

Finding the shortest path between a number of nodes (not just distance)

python-3.x

algorithm

graph

networkx

path-finding