Найти все одинаково кратчайшие пути с Dijkstra, используя очередь приоритетов

Question

Я хочу реализовать алгоритм Дейкстры, чтобы найти самый дешевый путь в графе между двумя узлами. Вес - это расстояние в X, Y между узлами. Я понимаю, как реализовать dijkstra, но мне нужно найти все пути, которые являются самыми короткими. Поэтому, если 2 пути имеют одинаковую длину, я хочу их обоих.

Я также посмотрел повсюду в Google и Stack Overflow. Но я не могу действительно обернуть голову вокруг некоторых из ответов, которые даны. Никто не использует приоритетную очередь. Я думал о маркировке узлов, которые мы уже посетили, но разве это не обрезает пути?

Это псевдокод из Википедии Я хочу реализовать.

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, вы должны найти все кратчайшие пути.

Что касается очереди с приоритетами, есть проблема, что вы выигрываете время, добавляя av к Q, но если вы измените av,Вы должны найти его в середине Q (медленно), удалив его там (медленно) и добавить измененную версию. Существуют структуры данных, которые делают этот процесс быстрее. Я использую приоритетные очереди, но я не удаляю измененные вершины. Я добавляю измененные вершины, не удаляя их старые версии. Если я выберу хороший Компаратор, версия с более коротким путем (или, если равно, более длинный предыдущий список) будет извлечена первой. Поэтому я должен проверить всех вас из Q на предмет посещения;если да, я могу выбросить тебя. По окончании Q ... вершина u должна быть отмечена как посещенная.