Доказывается, что значения расстояния, извлеченные в алгоритме Дейкстры, не уменьшаются?

Question

Я просматриваю свои старые алгоритмы и сталкиваюсь с этим доказательством. Это было из задания, которое у меня было, и я понял его правильно, но я чувствую, что доказательства, безусловно, не хватает.

Вопрос заключается в том, чтобы prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

Мое доказательство идет следующим образом:

Доказательство от противного. Кулак, предположим, , что мы вытаскиваем вершину из Q с d-value 'i'. В следующий раз мы потянем вершину с d-значением 'j'. Когда мы набрали , мы завершили наше d12-значение и вычислили кратчайший путь от начальной вершины s до i. С у нас есть положительные веса, это невозможно для наших значений d сжиматься , поскольку мы добавляем вершины к нашему пути. Если после вытягивания i из Q, мы вытаскиваем j с меньшим значением d, у нас может не быть кратчайшего пути 0, чтобы мы могли , чтобы достичь i-j. Однако мы уже вычислили кратчайший путь . Мы не проверяли возможный путь . У нас больше нет гарантированного пути . Противоречие.

Как можно улучшить это доказательство? Или еще лучше, есть ли другой подход? Это только кажется довольно слабым :)

Edit: К сожалению, в этом случае моя очередь приоритет реализуется с Min кучи

Answer 1

Давайте установим эти (это все верно, так как они, в основном, определение алгоритма):

1. Очередь Приоритет в алгоритме Дейкстры даст вам узел с наименьшим г-значения в каждой итерации алгоритма.
2. Нет отрицательных нагрузок.
3. Как только узел был удален, он никогда не вернется в очередь.
4. Значение d узла, которое было отменено, окончательно и не изменится с этой точки.

Продолжая (1), d-значение этого из очереди узла, предполагая, что (2) применяется, будет по крайней мере, равно предыдущему г-значением, извлеченным, так как d-значение каждого узла зависит на d-значениях узлов, выделенных до него, что является своего рода рекурсивным определением. Так как (3) и (4) верны, это рекурсивное определение заканчивается на стартовом узле с d-значением 0.
Итак, если d-значение каждого узла по крайней мере равно d-значению перед ним , и (1) все еще применяется, набор d-значений, извлеченных из очереди приоритетов, равен неубывающим.

(После прочтения этого, и то, что вы написали, это в основном то же самое, но представил немного лучше, я думаю)