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

Question

我有一个大约有 50000 个节点的未加权、无向网络，我需要从这个网络中提取任意一对节点之间的最短路径。我使用了 boost 库中的 dijkstra_shortest_paths 函数，它运行良好。后来才知道，在给定的一对节点A和B之间，可以有不止一条最短路径。在这种情况下，Dijkstra 函数如何在这些最短路径中进行选择？它取决于节点 ID 或这些节点在内存中的存储顺序吗？

我发现了一些关于如何提取两个节点之间的所有最短路径的问题，因为通常只提取其中一个，例如 this question and this question。但是，我不想提取两个节点之间的所有最短路径。相反，我想知道函数返回的路径究竟是如何在其他长度相同的最短路径中被拾取的。

我试图深入研究 boost 库中的相关源代码，但似乎对我来说太高级了，我很快就迷路了。另外，我用谷歌搜索找不到答案，所以我在这里问。

Answer 1

确切的算法是documented:

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 而无需修改图表。

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

How does boost graph dijkstra_shortest_paths pick the shortest path when there are multiple shortest paths between a specific pair of nodes?

c++

boost

graph

dijkstra

shortest-path