УЗЕЛ БРЕМЯ
О
ЧТОБЫ ДОБРАТЬСЯ ДО УЗЛА А, ТЕПЕРЬ ТРЕБУЕТСЯ 6СЕГ0 5 МИН
НАЧАЛО
КОНЕЦ
го, да мы обнаружили более короткий путь к узлу А! Раньше для перехода к нему требовалось 6 минут.
А
НАЧАЛО
КОНЕЦ
если идти через узел В, то существует путь, который занимает всего 5 минут!
Если вы нашли более короткий путь для соседа В, обновите его стоимость. В данном случае мы нашли:
Более короткий путь к А (сокращение с 6 минут до 5 минут).
Более короткий путь к конечному узлу (сокращение от бесконечности до 7 минут).
Шаг 3: повторяем!
Снова шаг 1: находим узел, для перехода к которому требуется наименьшее время. С узлом В работа закончена, поэтому наименьшую оценку времени имеет узел А.
УЗЕЛ БРЕМЯ
С
НАЧАЛО $■
*> КОНЕЦ
нова шаг 2: обновляем стоимости соседей А.
Путь до конечного узла теперь занимает всего 6 минут!
Алгоритм Дейкстры выполнен для каждого узла (выполнять его для конечного узла не нужно). К этому моменту вам известно следующее:
Чтобы добраться до узла В, нужно 2 минуты.
Чтобы добраться до узла А, нужно 5 минут.
Чтобы добраться до конечного узла, нужно б минут.
УЗЕЛ БРЕМЯ
П оследний шаг — вычисление итогового пути — откладывается до следующего раздела. А пока я просто покажу, как выглядит итоговый путь.
А
КРАТЧАЙШИЙ ПУТЬ С ПОИСКОМ 6 ШИРИНУ
лгоритм поиска в ширину не найдет этот путь как кратчайший, потому что он состоит из трех сегментов, а от начального узла до конечного можно добраться всего за два сегмента.
В
ЬЗВЕШЕННЫЙ ГРАФ
НЕ63ВЕШЕННЫЙ ГРАФ (ПОИСК 6 ШИРИНУ)
предыдущей главе мы использовали поиск в ширину для нахождения кратчайшего пути между двумя точками. Тогда под «кратчайшим путем» понимался путь с минимальным количеством сегментов. С другой стороны, в алгоритме Дейкстры каждому сегменту присваивается число (вес), а алгоритм Дейкстры находит путь с наименьшим суммарным весом.
На всякий случай повторим: алгоритм Дейкстры состоит из четырех шагов:
Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).
Проверить, существует ли более дешевый путь к соседям этого узла, и если существует, обновить их стоимости.
Повторять, пока это не будет сделано для всех узлов графа.
Вычислить итоговый путь (об этом в следующем разделе!).
Терминология
Я хочу привести еще несколько примеров применения алгоритма Дейкстры. Но сначала стоит немного разобраться с терминологией.
К огда вы работаете с алгоритмом Дейкстры, с каждым ребром графа связывается число, называемое весом.
Г
Do'stlaringiz bilan baham: |