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

Question

我正在尝试寻找通过图中指定节点的最短路径（A-> B-> C而不是仅A-> C）。当前，我的代码将返回最短路径，而不是通过所有指定的节点。

代码：

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具有两个旅行推销员功能，但是它们都不能返回路径，只能返回距离，所以我认为我不能使用它们。

Answer 1

您应该多次调用shortest_path，每个需要的子路径一次。因此，当请求为A-> B-> C时，请找到从A到B的最短路径，然后找到从B到C的最短路径，然后将两个结果连接起来。

multi_source_dijkstra的作用不同：它找到从源节点之一到目标节点的路径。