Алгоритм Дейкстры позволяет нам найти кратчайший путь между двумя вершинами графа. Здесь мы исследуем интуицию алгоритма — какую информацию нам нужно отслеживать, в каком порядке нам нужно исследовать вершины и каковы ограничения алгоритма.
Расшифровка видео
Поиск по видео
0:00
[музыка]
0:01
чтобы понять что такое алгоритм дестра и
0:03
как он работает Давайте начнём с такой
0:06
ситуации представим что у нас есть
0:08
множество разных городов разбросанных в
0:11
разных местах Некоторые из этих городов
0:13
связаны дорогами с другими городами и мы
0:17
можем путешествовать по дороге чтобы
0:19
добраться из одного города в другой
0:22
время в пути по разным дорогам может
0:23
быть разные то есть одна дорога может
0:26
занять 3 минуты в то время как другая
0:28
займёт четыре и наш вопрос заключается в
0:31
следующем Какой самый быстрый маршрут из
0:35
города А в город
0:38
Б этот конкретный пример часть общей
0:41
задачи в теории графов где у нас есть
0:44
вершины в данном случае наши города
0:47
которые соединены рёбрами в данном
0:49
случае это наши дороги вместе вершины и
0:53
рёбра образуют Граф в частности этот
0:56
Граф является взвешенным графом потому
0:59
что каждая ребро имеет некоторое
1:01
значение или вес указывающее Как дорого
1:04
обходится проход по этому ребру вес
1:06
измеряется либо расстоянием либо
1:08
временем и с помощью этого графа Мы
1:11
хотим определить кратчайший маршрут от
1:13
одной вершины к
1:15
другой Итак как алгоритм де экстры
1:18
позволит нам это сделать Мы хотим
1:20
выяснить сколько минут займёт кратчайший
1:23
путь до города
1:24
б но возможно в процессе нам также будет
1:28
полезно выяснить сколько минут займёт
1:30
кратчайший путь до других городов
1:33
Поэтому в идеале Мы хотим для каждого
1:35
города записать минимальное время за
1:38
которое мы можем до него добраться
1:40
конечно пока мы не знаем этой информации
1:43
поэтому мы будем записывать минимальное
1:45
время которое мы сможем найти которое
1:48
нам потребуется чтобы добраться до этого
1:51
города изначально мы не знаем ни одного
1:54
способа добраться до других городов
1:57
поэтому мы потим все их бесконечно
2:00
единственный город про который мы хоть
2:02
что-то знаем это наш стартовый город
2:04
город а тут совсем просто мы начинаем с
2:07
этого города А значит нам нужно но минут
2:09
чтобы добраться до него как только мы
2:12
найдём кратчайший маршрут до какого-то
2:14
города Давайте скажем что этот город
2:17
изучен А все остальные города мы назовём
2:20
неизученные потому что нам неизвестно
2:22
кратчайшего маршрута до
2:25
них Итак что дальше
2:30
два
2:31
шага Первое — это обновление оценок а
2:34
второе — это выбор следующей вершины для
2:38
изучение Давайте начнём с первого шага
2:41
обновим оценки мы знаем что мы можем
2:44
добраться до города А за но минут у нас
2:46
есть дорога ценой 3 минуты Из города А в
2:49
город с Значит мы можем добраться до
2:53
города с за 3 минуты конечно это сильно
2:56
лучше чем бесконечность поэтому Давайте
2:58
обновим оценку в городе c до
3:01
ТХ А теперь давайте сделаем то же самое
3:04
для города F мы можем добраться до этого
3:07
города за две
3:09
минуты после этого мы изучили все
3:12
возможные дороги из города А поэтому с
3:14
первым шагом закончено на следующем шаге
3:17
нам нужно выбрать новую вершину для
3:20
изучения Это довольно
3:22
просто следующий город для изучения —
3:25
это город с наименьшей оценкой который
3:28
мы ещё не успели изучить
3:30
ранее другими словами следующий город
3:33
для изучения должен быть городом
3:35
неизученный ранее в которым можем
3:38
добраться быстрее всего в нашем случае
3:41
это город F в который мы добираемся за 2
3:44
минуты а теперь шаги алгоритма дест
3:47
будут повторяться снова для начала
3:50
обновим оценки для городов которые можно
3:52
попасть из города F нам нужно 5 минут
3:56
чтобы добраться из города F в город G
3:59
значит если мы умеем добираться до
4:01
города F за 2 минуты то нам нужно 7
4:04
минут чтобы добраться до города G сумма
4:06
этих двух
4:08
значений также мы можем добраться до
4:10
города б за 8 минут и до города е за 5
4:14
минут также мы можем добраться до города
4:17
с за 4 минуты 2 минуты чтобы добраться
4:20
до города F и ещё 2 минуты чтобы
4:22
добраться до города с но 4 минуты — это
4:26
хуже текущей оценки для города с которая
4:31
поэтому мы не будем ничего обновлять
4:34
напомню что для города мы храним
4:36
минимальное возможное время маршрута
4:39
который на данный момент у нас есть Итак
4:43
продолжим на втором шаге алгоритма де
4:45
ист выберем следующую вершину среди
4:48
неисследованный вершин с наименьшим
4:50
временем в нашем случае это город си в
4:54
которой мы можем добраться за 3 минуты и
4:57
процесс повторяется снова 3 минуты до
4:59
города с Значит нам нужно 4 минуты до
5:02
города D и Мы также можем добраться до
5:04
города е за 4 минуты 3 минуты до города
5:07
с плюс 1 минута из города с Мы видим что
5:11
4 минуты — это лучше текущего значения 5
5:15
минут поэтому обновим оценку с пяти до
5:19
четырёх следующим городом для изучения
5:22
будет город е среди всех неизученный
5:24
городов у него самое наименьшее
5:27
значение давайте заметим что Каждый раз
5:30
когда мы изучаем Новый город мы
5:32
гарантируем что мы нашли кратчайший
5:34
маршрут чтобы добраться до этого города
5:37
поскольку если существует маршрут Короче
5:40
мы бы изучили этот маршрут сначала
5:42
потому что у нас приоритет на изучение
5:44
минимальных значений и через город е мы
5:48
можем добраться до города б всего за 6
5:50
минут 4 минуты до города Е плюс 2 минуты
5:54
из города е поэтому мы обновим нашу
5:57
оценку для города б на сть что лучше чем
6:00
предыдущая оценка
6:01
восем и теперь следующий город для
6:04
посещения — город Б наш пункт назначения
6:08
это говорит нам что наименьшее время
6:10
чтобы добраться из города А до города б
6:13
составляет 6 минут и это алгоритм де
6:17
экстры для нахождения кратчайших путей в
6:20
графе есть несколько вещей про которые
6:22
ещё нужно сказать во-первых технически
6:26
наш алгоритм говорит нам только о
6:27
времени которое потребуется чтобы
6:30
добраться из города А до города Б И на
6:32
самом деле не говорит по какому маршруту
6:34
надо двигаться чтобы действительно
6:36
восстановить маршрут нам нужно добавить
6:39
ещё Шаг к нашему алгоритму Каждый раз
6:42
когда мы обновляем оценку для города нам
6:44
нужно запомнить город из которого мы
6:47
пришли когда смогли Получить новую
6:49
оценку если мы запомним это направление
6:52
для каждого города в процессе нашего
6:54
алгоритма тогда в конце мы сможем
6:57
выяснить Какой маршрут является лучшим
7:00
просто двигаясь по стрелочкам из Конца в
7:02
начало также стоит отметить что алгоритм
7:05
будет работать корректно только если
7:08
веса всех рёбер будут
7:10
неотрицательны поскольку в противном
7:12
случае ребро отрицательного веса может
7:15
образовать кратчайший маршрут Который
7:17
наш алгоритм не сможет
7:19
найти ещё одна вещь о которой нужно
7:21
подумать это то Как эффективно мы
7:23
находим следующий неизученный город для
7:25
посещения Мы всегда хотим выбирать
7:28
неизученный город наименьшей оценкой
7:31
например какой-нибудь вид приоритетной
7:33
очереди которая позволит нам эффективно
7:36
находить следующий город делает наш
7:38
алгоритм
7:39
быстрее вот он алгоритм дестри для
7:42
нахождения кратчайших путей в графе мы
7:45
будем поддерживать расстояние и
7:47
предыдущий город для каждой вершины
7:50
расстояние для всех вершин начинается с
7:52
бесконечности только у стартовой вершины
7:55
это ноль и затем пока мы не изучили наш
7:58
конечный пункт
8:00
Мы выбираем вершину с наименьшим
8:02
расстоянием для следующего
8:04
исследования рассматриваем все рёбра
8:06
Соединённые с этой вершиной И если мы
8:10
можем получить более короткий маршрут
8:12
для соседней вершины тогда мы обновим
8:14
оценку расстояние и запомним вершину из
8:17
которой пришли как только мы изучим
8:19
конечный пункт мы будем знать как быстро
8:22
мы сможем добраться до конечного пункта
8:24
А также найдём кратчайший
8:28
маршрут Y
8:30
[музыка]