Networkx中选择最短路径的明确性

Question

我有一个图表：

为什么用了最短路径函数后：

nx.shortest_path(g, 0, 6)

为什么输出路径是[0, 3, 6]？为什么不 [0, 2, 6]？在上述情况下，算法 shortest_path() 的路径选择 [0, 3, 6] 是否总是明确的？

Answer 1

@jon-clements 在问题的评论中有正确答案。如果有多条最短路径，函数 networkx.shortest_path() 将 return 其中之一。您获得的具体路径取决于数据在 networkx 图形数据结构（基于 Python 字典）中的存储方式，并且不保证是确定性的。如果愿意，您可以获得所有最短路径，甚至可以对它们进行排序以提供稳定的顺序 - 例如

In [1]: import networkx as nx

In [2]: G = nx.Graph({0: [3, 2], 2: [6, 4], 3: [5, 6]})

In [3]: nx.shortest_path(G, 0, 6)
Out[3]: [0, 2, 6]

In [4]: list(nx.all_shortest_paths(G, 0,6))
Out[4]: [[0, 3, 6], [0, 2, 6]]

In [5]: sorted(nx.all_shortest_paths(G, 0,6))
Out[5]: [[0, 2, 6], [0, 3, 6]]

Networkx中选择最短路径的明确性

The unambiguity of choosing the shortest path in Networkx

python

shortest-path

networkx