python-3.x - 在 python 中使用 networkx 包的 K-最短路径

Question

我使用 osmnx 包创建了荷兰高速公路的多向图。

该图是从 osmnx 返回的多向图。由于我有兴趣计算起点和终点之间的 k 最短路径，因此我尝试了 networkx 库。但是，networkx 似乎不适用于多向图。我只能计算最短路径。

我想问一下是否有任何其他方法可以在多向图上在 python 中执行 k 最短路径计算。

Answer 1

尝试使用 networkx 命令shortest_simple_paths（文档）。

它返回一个生成器，该生成器一次返回一条从最短到最长的路径。

G = nx.karate_club_graph()
X = nx.shortest_simple_paths(G, 0, 5)
k = 5
for counter, path in enumerate(X):
     print(path)
     if counter == k-1:
         break
> [0, 5]
> [0, 6, 5]
> [0, 10, 5]
> [0, 6, 16, 5]
> [0, 4, 6, 5]

这将适用于DiGraphs，但我不确定 a MultiDiGraph。但是，我不清楚道路网络是否会是 MultiDiGraph。