Почему алгоритм Дейкстры корректен?

Question

[NightFantom]

Всем привет. Ребята, я что-то не догоняю корректность алгоритма Дейкстры. Есть такой граф:


После выполнения алгоритма, мы получим, что кратчайшее расстояние до второй вершины равно 10. Хотя кратчайший путь равен 2. Как так?

Answer 1

[Дмитрий Филимонов]

На первой итерации вес вершины 1 равен 0. От нее идем к соседям. До 3 вершины вес равен 1. До 2 вершины вес равен 10. Больше к 1 вершине не идем, она с минимальным весом. Следующая оставшаяся с минимальным из соседей - это 3. Выбираем её. Путь только в одну сторону - к 2 - и вес равен 2 (суммируется предыдущий вес). Раньше дотуда был вес 10, но так как наш новый вес меньше, заменяем на меньший. Выбираем вершину 2, а от нее уже некуда идти.

Итого кратчайший путь до вершины 2 составляет 2 и идет через соседа 3 (если бы мы запоминали это во время итераций). По ребру с весом 10 вообще ничего не пойдет в данном случае.

Comments

[NightFantom]

Спасибо! Теперь понял в чём у меня была проблема.

Answer 2

[throughtheether]

После выполнения алгоритма, мы получим, что кратчайшее расстояние до второй вершины равно 10.

Вот здесь непонятно, поясните вашу мысль.

Изначально (стартуем из вершины 1) у вас вершина 1 имеет ассоциированное число (длину пути, d[1]) 0, она же находится во множестве посещенных вершин. Длина пути до других вершин - бесконечность.
Для всех ребер, соединяющих множества посещенных и непосещенных вершин (т.е. для ребер 1-2 и 1-3) рассмотрим суммы d[u]+w(u,v), где d[u]-длина кратчайшего пути до вершины u, w(u,v) - вес (длина) соответствующего ребра. Минимальная сумма наблюдается для ребра 1-3, соответствующего пути 1,3. Добавляем 3 в посещенные.
Снова, для всех ребер, соединяющих множества посещенных и непосещенных вершин (т.е. для ребер 1-2, 3-2) рассматриваем соответствующие суммы (10 и 2), выбираем минимальную, т.е. добавляем вершину 2 в путь (и во множество посещенных вершин), имеющий вид 1,3,2. Так как непосещенных вершин не осталось, завершаем работу алгоритма.

Comments

[NightFantom]

Спасибо! Теперь понятно в чём у меня была проблема. Я не правильно понял объяснение алгоритма с википедии :)

[throughtheether]

NightFantom: Рекомендую на эту тему курс по алгоритмам от Coursera с Tim Roughgarden в качестве лектора. Очень понятно объясняет.