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

Question

我想实现dijkstra的算法，在两个节点之间的图中找到最便宜的路径。权重是节点之间的距离，单位为X，Y。我知道如何实现dijkstra，但我需要找到最短的所有路径。所以如果两条路径是相同的长度，我希望他们两个。

我也在谷歌和堆栈溢出上到处找。但是我真的不能理解给出的一些答案。也没有人使用优先级队列。我在考虑标记我们已经访问过的节点，但这不会切断路径吗？

这是我要实现的来自维基百科的伪代码。

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==target时不会停止，因此您应该找到所有最短路径。

关于优先级队列，有一个问题，你可以通过在Q中添加一个v来获得时间，但是如果你改变了一个v，你必须在Q的中间找到它（慢），把它移走（慢），然后添加改变的版本。有一些数据结构可以更快地处理这个问题。我使用优先级队列，但我不删除更改的顶点。我添加更改的顶点而不删除它们的旧版本。如果我选择了一个好的比较器，具有较短路径的版本（或者，如果相等，较长的先前列表）将首先被拉动。所以我必须测试Q中的所有u是否被访问；如果是，我可以把你扔掉。在结束时Q...顶点u必须被标记访问。