python图寻找替代的最快路径

Question

我有一个非常大的网络（整个国家的公路网），我将其加载到networkx中，以计算点之间的距离。如果我只想知道两点之间最快的路线，这个方法很好而且非常快。但是，我也想知道路线的备选方案（如果一条路线是1000公里，我还想知道1010公里、1018公里、1032公里和1042公里的备选路线）。我曾考虑过使用networkx的all_simple_paths函数，但这确实很慢，需要几天才能运行。有人能提出另一种方法吗？在

谢谢！在

Answer 1

Networkx有一个内置算法，可以生成最短路径、下一个最短路径、下一个最短路径等

它是shortest_simple_paths。在

例如：

import networkx as nx
G = nx.Graph()
G.add_edges_from([[0,1], [1,2], [2,3], [0,2], [0,3]])
X = nx.shortest_simple_paths(G, 0, 3) #generator to find paths from 0 to 3 in order from shortest to longest.
for x in X:
    print(x)
> [0, 3]
> [0, 2, 3]
> [0, 1, 2, 3]
#note that X is now empty because it is a generator
for x in X:
    print(x) #nothing to see here
> 
#if you just want the first two:
X = nx.shortest_simple_paths(G, 0, 3)
for k in range(2):
    print(next(X))
> [0, 3]
> [0, 2, 3]

该算法可以找到所有的路径，但它的设置是这样的：当被要求时，它只做额外的工作来计算第k条最短路径，然后忘记它。有关生成器的更多信息，请参见Understanding generators in Python。在