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

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

2 голосов
/ 14 апреля 2010

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

Вопрос к prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

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

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

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

Редактировать: Извините, в этом случае моя очередь с приоритетами реализована с минимальной кучей

1 Ответ

1 голос
/ 14 апреля 2010

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

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

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

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

...