Грокаем а Иллюстрированное пособие для программистов и любопытствующих

А
^5
В	2
КОНЕЦ

УЗЕЛ БРЕМЯ

О

ЧТОБЫ ДО­БРАТЬСЯ ДО УЗЛА А, ТЕПЕРЬ ТРЕБУЕТСЯ 6СЕГ0 5 МИН



НАЧАЛО


КОНЕЦ


го, да мы обнаружили более короткий путь к узлу А! Раньше для перехода к нему требовалось 6 минут.
А
НАЧАЛО


КОНЕЦ


если идти через узел В, то существует путь, который занимает всего 5 минут!
Если вы нашли более короткий путь для соседа В, обновите его стоимость. В данном случае мы нашли:

• 
  Более короткий путь к А (сокращение с 6 минут до 5 минут).
  
• 
  Более короткий путь к конечному узлу (сокращение от бесконечности до 7 минут).
  

Шаг 3: повторяем!
Снова шаг 1: находим узел, для перехода к которому требуется наименьшее время. С узлом В работа закончена, поэтому наименьшую оценку времени имеет узел А.

УЗЕЛ БРЕМЯ

А	5
В	г
КОНЕЦ	9

С
НАЧАЛО $■


*> КОНЕЦ


нова шаг 2: обновляем стоимости соседей А.
Путь до конечного узла теперь занимает всего 6 минут!
Алгоритм Дейкстры выполнен для каждого узла (выполнять его для конеч­ного узла не нужно). К этому моменту вам известно следующее:

• 
  Чтобы добраться до узла В, нужно 2 минуты.
  
• 
  Чтобы добраться до узла А, нужно 5 минут.
  
• 
  Чтобы добраться до конечного узла, нужно б минут.
  

УЗЕЛ БРЕМЯ

А	S
В	2
КОНЕЦ	6

П
оследний шаг — вычисление итогового пути — откладывается до следую­щего раздела. А пока я просто покажу, как выглядит итоговый путь.
А
КРАТЧАЙШИЙ ПУТЬ С ПОИСКОМ 6 ШИРИНУ

лгоритм поиска в ширину не найдет этот путь как кратчайший, потому что он состоит из трех сегментов, а от начального узла до конечного можно добраться всего за два сегмента.
В
ЬЗВЕШЕННЫЙ ГРАФ


НЕ63ВЕШЕННЫЙ ГРАФ (ПОИСК 6 ШИРИНУ)

предыдущей главе мы использовали поиск в ширину для нахождения кратчайшего пути между двумя точками. Тогда под «кратчайшим путем» понимался путь с минимальным количеством сегментов. С другой стороны, в алгоритме Дейкстры каждому сегменту присваивается число (вес), а ал­горитм Дейкстры находит путь с наименьшим суммарным весом.
На всякий случай повторим: алгоритм Дейкстры состоит из четырех шагов:

1. 
   Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).
   
2. 
   Проверить, существует ли более дешевый путь к соседям этого узла, и если существует, обновить их стоимости.
   
3. 
   Повторять, пока это не будет сделано для всех узлов графа.
   
4. 
   Вычислить итоговый путь (об этом в следующем разделе!).
   

Терминология
Я хочу привести еще несколько примеров применения алгоритма Дейкстры. Но сначала стоит немного разобраться с терминологией.
К
огда вы работаете с алгоритмом Дейкстры, с каждым ребром графа свя­зывается число, называемое весом.
Г