boost graph dijkstra_shortest_paths如何在特定对节点之间存在多条最短路径时选择最短路径

Question

我有一个大约50000个节点的未加权无向网络，我需要从这个网络中提取任何一对节点之间的最短路径。我使用了boost库中的dijkstra_shortest_paths函数，它工作得很好。后来我意识到，在给定的一对节点之间，a和B，最短路径可能不止一条。在这种情况下，Dijkstra函数如何从这些最短路径中选择?它是否依赖于节点id或这些节点在内存中的存储顺序?

我发现了一些问题，询问如何提取两个节点之间的所有最短路径，因为通常只提取其中一个，例如这个问题和这个问题。但是，我不想提取两个节点之间的所有最短路径。相反，我想知道函数返回的路径是如何从其他具有相同长度的最短路径中挑选出来的。

我试图更深入地了解boost库中的相关源代码，但似乎它对我来说太先进了，我很快就迷路了。另外，我在谷歌上也找不到答案，所以我在这里问。

Answer 1

详细的算法如下:

DIJKSTRA(G, s, w)
for each vertex u in V (This loop is not run in dijkstra_shortest_paths_no_init)
d[u] := infinity
p[u] := u
color[u] := WHITE
end for
color[s] := GRAY
d[s] := 0
INSERT(Q, s)
while (Q != Ø)
u := EXTRACT-MIN(Q)
S := S U { u }
for each vertex v in Adj[u]
if (w(u,v) + d[u] < d[v])
d[v] := w(u,v) + d[u]
p[v] := u
if (color[v] = WHITE)
color[v] := GRAY
INSERT(Q, v)
else if (color[v] = GRAY)
DECREASE-KEY(Q, v)
else
...
end for
color[u] := BLACK
end while
return (d, p)

在链接页面中突出显示事件发生的位置。

由此可见，发现顶点的顺序决定了你的答案。

您可以通过指定自定义比较(CompareFunction)来实现其他tie-breakers，而无需修改图。