Тренировки по алгоритмам 4.0. Лекция 3: Кратчайшие пути во взвешенных графах

Не нравится, какие маршруты прокладывает Навигатор? Если вы научитесь искать кратчайшие пути в графах, то сможете написать свой.

[Nyamerka]

Спасибо большое за Ваши лекции и в целом за такую возможность проходить тренировки. Лучшие просто!

[SvetaMelekhina]

Отсылка к ведьмаку, неожиданно приятно. Спасибо за лекцию!

[yuliana_karavaeva]

0:35 - Идея алгоритма Дейкстры
12:30 - Хранение графа
20:23 - Корректность алгоритма Дейкстры
25:52 - Сложность алгоритма Дейкстры
30:01 - Ускорение алгоритма Дейкстры
43:54 - Применение алгоритма Дейкстры
1:07:37 - Ответы на вопросы

[intention-man]

Хорошо будет, если зону презентации увеличите на экране трансляции. А так все классно)

[jafonoksy]

В доказательстве корректности алгоритма ошибка. Дело в том, что для того, чтобы доказать, что dist[v] действительно минимальное расстояние до v, мы пользуемся тем, что dist[u] - действительно минимальное расстояние до u, но мы это не знаем.

Верное доказательство состоит в том, что мы будем поддерживать то, что dist[x] для вершинки x, которая лежит в visited расстояние посчитано корректно в каждый момент времени. В начале это очевидно правда. Далее, пусть v вершинка вне visited у которой минимальный dist[v], а вершинка u - с минимальным расстоянием до исходной опять же вне visited. Пусть в пути от исходной до u, перед u была w. Тогда если w не в visited, то расстояние до w меньше чем до u, что противоречит определению u*. Поэтому w в visited. Но тогда, расстояние до u это dist[u] по построению dist, а значит dist[u] = dist[v]. Теперь пусть w_1 вершинка перед v в оптимальном пути до v. Если она в visited, то все опять же хорошо, иначе расстояние до v, это расстояние до w_1 + ребро из w_1 в v. Но расстояние до w_1 не меньше чем расстояние до u, которое равняется dist[u] = dist[v]. Поэтому расстояние до v с одной стороны не больше чем dist[v], но с другой стороны расстояние равное dist[v] существует. Значит действительно переход корректен.

*тут тоже может быть случай dist[w] = dist[u], но давайте брать u минимальным не только по расстоянию с весами, но и по расстояние по вершинкам, тогда все будет ок

[my_learning_spaceship]

Вялікі дзякуй за гэтыя лекцыі/заняткі. Вельмі дапамагае арыентавацца і знаходзіць новы матэрыял