使用优先级队列使用Dijkstra查找所有相等的最短路径

Question

我想实现dijkstra的算法，以在两个节点之间的图中找到最便宜的路径。权重是节点之间以X，Y表示的距离。我了解如何实现dijkstra，但是我需要找到所有最短的路径。因此，如果2条路径的长度相同，我都希望它们都具有。

我在Google和Stack Overflow上也到处都看过。但是我无法真正回答给出的一些答案。也没有人使用优先级队列。我当时正在考虑标记已经访问过的节点，但这不会切断路径吗？

这是我要实现的Wikipedia中的伪代码。

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                           // Initialization
3
4      create vertex priority queue Q
5
6      for each vertex v in Graph:           
7          if v ≠ source
8              dist[v] ← INFINITY                 // Unknown distance from source to v
9          prev[v] ← UNDEFINED                    // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                      // The main loop
15         u ← Q.extract_min()                    // Remove and return best vertex
16         for each neighbor v of u:              // only v that are still in Q
17             alt ← dist[u] + length(u, v) 
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

[如果有人提出建议，或者如果不是优先队列，请告诉我。谢谢。

Answer 1

如果prev []不是一个顶点而是一个顶点列表，您可能会得到想要的东西。在第20行中，您将创建一个仅包含u的新列表。另外（可能在17到18之间），如果alt == dist [v]，则将u添加到prev [v]。由于当v ==目标时此伪代码不会停止，因此您应该找到所有最短路径。

关于优先级队列，存在一个问题，通过在Q上添加av可以节省时间，但是如果更改av，则必须在Q的中间（慢）找到它，然后在Q的中间删除（慢）并添加更改版本。有些数据结构可以更快地完成该过程。我使用优先级队列，但我不删除更改的顶点。我添加了更改的顶点，而没有删除它们的旧版本。如果我选择一个好的比较器，则会首先拉出路径较短（或相等，则较长的上一个列表）的版本。因此，我必须测试来自Q的所有u是否被访问；如果是的话，我可以把你扔掉。在Q ...顶点结束时，必须标记访问u。