Finding all equally shortest paths with Dijkstra using a Priority Queue

Question

I want to implement dijkstra's algorithm to find the cheapest path in a graph between two nodes. The weight is the distance in X,Y between nodes. I understand how to implement dijkstra, but I need to find all paths that are the shortest. So If 2 paths are the same length, I want them both.

I have looked everywhere on Google and Stack Overflow as well. But I can't really wrap my head around some of the answers that are given. Nor does anybody use a Priority Queue. I was thinking about marking Nodes that we're already visited, but wouldn't this cut off paths?

This is the pseudo-code from Wikipedia I want to implement.

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

If anybody has suggestions or maybe if a priority queue is not the way to go, please let me know. Thank you.

Answer 1

You might get what you want if prev[] is not a vertex but a list of vertex. In line 20, you create a new list containing only u. Additionally (perhaps between 17 and 18), if alt == dist[v], you add u to prev[v]. As this pseudocode does not stop when v == target, you should find all shortest paths.

Concerning the priority queue, there is the problem that you gain time by adding a v to Q, but if you change a v, you have to find it in the middle of Q (slow), removing it there (slow) and add the changed version. There are data structures that do that process faster. I use priority queues, but i do not remove changed vertices. I add changed vertices without removing their old versions. If i choose a good Comparator, the version with the shorter path (or, if equal, the longer prev list) will be pulled first. So i have to test all u from Q for being visited; if yes, i can throw u away. At the end of while Q ... vertex u has to be flagged visited.