Как алгоритм кратчайшего пути Дейкстры работает с приоритетными очередями?

Question

Я читал веб-сайты в Интернете, и все говорят, что использование очереди с приоритетами принесет пользу, но я не понимаю, что здесь используется в качестве "приоритета".

В самом начале, является ли первый элемент в очереди приоритетов всегда узлом начальной точки? Если так, когда мы извлекаем начальный узел с расстоянием 0, как мы получаем его соседей из очереди приоритетов?

Answer 1

Очередь приоритетов Q хранит набор отдельных элементов. Каждый элементx имеет связанный ключ x.key

Когда Дейкстра основан на очереди приоритетов. Затем мы сохраняем вершины в очереди, расстояния которых от источника еще не определены, с учетом их текущего расстояния от источника.

Взгляните на этот PDF-файл, где алгоритм основан на абстрактной структуре данных, называемой очередью приоритетов, которая может быть реализована с использованием двоичной кучи.

http://www.cs.bris.ac.uk/~montanar/teaching/dsa/dijkstra-handout.pdf

Answer 2

При реализации алгоритма Дейкстры вы используете очередь с приоритетами, чтобы определить порядок посещения узлов.

Очередь приоритетов содержит все не посещенные узлы и позволяет удалить (и затем обработать) узел с наименьшим назначенным расстоянием.

Очередь приоритетов является критически важной, поскольку она гарантирует, что узел никогда не посещается до тех пор, пока его назначенное расстояние не будет точным, а самый короткий из известных ему путей фактически является самым коротким путем. Это означает, что вам никогда не придется посещать и обрабатывать какой-либо узел дважды!

Обратите внимание, однако, что алгоритм Дейкстры может уменьшить назначенное расстояние узла много раз, прежде чем он будет посещен. Это означает, что очередь приоритетов должна динамически поддерживать увеличение приоритета узлов. Очереди со стандартным приоритетом, предоставляемые в Java и C++, НЕ поддерживают эту операцию и не могут использоваться в алгоритме Дейкстры. Вместо этого вы должны реализовать свою очередь приоритетов самостоятельно, используя кучу внутри ArrayList или std::vector.