Дистанционная подготовка: Вопрос по доказательству корректности алгоритма Дейкстры.
Вопрос по доказательству корректности алгоритма Дейкстры.
от Никита Пушкин - Воскресенье 1 Февраль 2015, 22:05
  У меня возник вопрос по доказательству верности алгоритма Дейкстры. Оно строится на том, что кратчайший путь P к вершине v можно разбить на две части: P1, состоящий только из помеченных вершин (как минимум стартовая вершина s будет в этом пути), и остальная часть пути P2 (она тоже может включать помеченные вершины, но начинается обязательно с непомеченной). Далее в доказательстве обозначают через p первую вершину пути P2, а через q — последнюю вершины пути P1.

Однако, по-моему мнению, если на текущей итерации мы выбираем вершину v, а не p, то вершина p попросту не может являться частью кратчайшего пути до v, иначе она уже была бы отмечена. Рассмотрим, например, некоторый другой путь P3 до вершины v, который не включает в себя точку p. Если путь P является кратчайшим путем до v, то как минимум должно выполняться следующее условие: длина пути P3 должна быть больше длины пути до v. А это значит, что точка p должна быть выбрана раньше, чем точка v, иначе кратчайший путь не проходит через точку p.
Возникают сомнения по поводу дальнейшего доказательства. Буду благодарен, если вы укажите мне на мою ошибку.