Как отслеживать кратчайшие пути в алгоритме Дейкстры при использовании очереди с минимальным приоритетом?

Question

Я пытаюсь реализовать алгоритм Дейкстры с приоритетной очередью.

Насколько я понимаю, «алгоритм Дейкстры» позволяет находить кратчайшие «пути», поскольку он возвращает набор вершин, образующих кратчайший путь *.

Из этого ответа здесь https://stackoverflow.com/a/20217659/1663462,, а также ( Dijkstra's_algorithm # Algorithm ) кажется, что я должен быть в состоянии реализовать его, используя только две структуры данных: график и очередь данных.

---

Однако, в моей реализации, использующей две упомянутые структуры данных, когда я наконец достигаю узла назначения, у меня не сохраняется путь к вершинам? Другими словами, у меня только самое короткое значение distance (одно скалярное значение).

Как это нужно отслеживать? Единственный способ, о котором я могу думать, - это использовать дополнительную структуру данных - массив или хэш-карту, где key будет вершина, а value будет ее родителем.

---

Актуальный вопрос:

Необходима ли дополнительная структура данных (" набор вершин, образующих кратчайший путь *")? Если нет, как я могу определить вершины?

Answer 1

Вам не нужно отслеживать весь путь для каждой вершины, как вы предлагали.Чтобы получить s-v сами пути, единственное, что вам нужно записать для каждой вершины v, - это ребро, которое "открыло" ее.

Другими словами, когда вершина v обнаруживаетсяПо алгоритму вы записываете ребро (u,v), на котором оно достигло значения, которое минимизировало расстояние от s.

Теперь, предполагая, что у вас есть «открывающее» ребро для каждой вершины v вНа графике путь от s до v можно вычислить следующим образом: если (u,v) - это ребро («обнаружение»), сохраненное для v, то кратчайший путь от s до v - этопуть от s до u (который может быть вычислен рекурсивно), за которым следует одно ребро (u,v).

Итак, чтобы построить кратчайший путь от s до v, вы начинаетев вершине v, затем вы следуете за ребром, сохраненным для v в обратном направлении, и продолжаете, пока не достигнете s.

Answer 2

Да, необходима дополнительная структура данных, я не нашел способа обойтись без нее.

Можно получить кратчайшее «расстояние» без него между двумя вершинами, но оно не будет включать в себя список вершин между исходной и конечной вершинами.