почему PriorityQueue используется в алгоритме Дейкстры?

Question

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

После посещения одной вершины, почему мы должны хранить соседние вершины в PriorityQueue вместо обычная очередь?

Причина, по которой я задаю вышеуказанный вопрос, была следующей: я понимаю, что с PriorityQueue мы можем получить либо самые большие / самые маленькие числа из очереди. Но в случае алгоритма Дейкстры мы в любом случае посещаем все вершины независимо от расстояния / приоритета. В таких случаях, почему нам нужно использовать PriorityQueue со сложностью O (log N), где обычная очередь будет делать O (1)?

Я что-то упустил?

Answer 1

Смысл алгоритма Дейкстры (а также BFS) заключается в том, что когда узел выходит из очереди приоритетов (или очереди FIFO в BFS), он должен иметь самое короткое расстояние от исходного узла, и расстояние будет заблокировано. Эти узлы будут помечены как посещенные и никогда не будут go в очередь снова. Вот почему очередь FIFO отлично работает в BFS, потому что веса каждого ребра равны, а кратчайшее расстояние от источника будет минимальным числом «прыжков».

Теперь давайте рассмотрим этот взвешенный граф:

       (s)
       / \
     2/   |
     /    |
   (a)    |
    |     |
   3|     |
    |     |
   (b)    |100
    |     |
   2|     |
    |     |
   (c)    |
    \     |
    4\    |
      \  /
      (d)

Давайте попробуем очередь FIFO, чтобы найти кратчайший путь от узла s.

       Push s:           Queue: [s],    Distance: s:0
Pop s, Push a, d:        Queue: [a, d], Distance: s:0, a:2, d:100
Pop a, Push b:           Queue: [d, b], Distance: s:0, a:2, d:100, b:5
Pop d, Push c:           Queue: [b, c], Distance: s:0, a:2, d:100, b:5, c:104
Pop b, No new neighbors, Queue: [c],    Distance: s:0, a:2, d:100, b:5, c:104
Pop c, No new neighbors, Queue: [],     Distance: s:0, a:2, d:100, b:5, c:104

Очевидно, что это неправильно для узлов c и d, где наименьшее расстояние будет 7 и 11 . Использование очереди с приоритетами определенно сделало бы это правильно.

Answer 2

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

Рассмотрим следующий график:

 a
 |\
1| \3
 |  \
 c---b
   1  \
       \
       ...

Когда мы посещаем вершину a, мы помещаем вершину b и вершину c в очередь приоритетов с расстояниями 3 и 1 соответственно. Если мы не используем приоритетную очередь, мы можем сначала посетить b, что является проблемой, потому что кратчайшее расстояние до b, которое мы знаем в настоящее время, является неоптимальным.

Если мы используем приоритетную очередь, мы может доказать, что когда мы исследуем вершину, нет пути к этой вершине короче, чем расстояние, которое мы знаем в настоящее время. Предположим ради противоречия, что мы посещаем вершину b, когда путь к ней короче. Пусть (u, v) будет ребром на более коротком пути к b, так что u был посещен, а v не был посещен. Так как u был посещен, мы должны были добавить v в очередь, и поскольку v находится на более коротком пути к b, его расстояние должно быть меньше, чем расстояние до b, что означает, что оно должно были посещены до b. Поэтому у нас есть противоречие, и мы знаем, что не может существовать более короткий путь.