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

В этой главе

• 
  Мы продолжим изучение графов и познакомимся со взвешенными графами, в которых некоторым ребрам назначаются большие или меньшие веса.
  
• 
  Вы изучите алгоритм Дейкстры, который позволяет получить ответ на вопрос «Как выглядит кратчайший путь к X?» для взвешенных графов.
  
• 
  Вы узнаете о циклах в графах, для которых алгоритм Дейкстры не работает.
  

В предыдущей главе вы узнали, как найти путь из точки А в точку В.
Найденный путь не обязательно окажется самым быстрым. Этот путь считается кратчайшим, потому что он состоит из наименьшего количества

лгоритм Дейкстры
сегментов (три сегмента). Но предположим, с каждым сегментом связыва­ется продолжительность перемещения. И тогда выясняется, что существует и более быстрый путь.



В предыдущей главе рассматривался поиск в ширину. Этот алгоритм нахо­дит путь с минимальным количеством сегментов (граф на первом рисунке). А если вы захотите найти самый быстрый путь (второй граф)? Быстрее всего это делается при помощи другого алгоритма, который называется алгоритмом Дейкстры.
Работа с алгоритмом Дейкстры
Посмотрим, как этот алгоритм работает с графом.

Каждому ребру назначается время перемещения в минутах. Алгоритм Дейкстры используется для поиска пути от начальной точки к конечной за кратчайшее возможное время.

Применив к этому графу поиск в ширину, вы получите следующий крат­чайший путь.
Э