Грокаем алгоритмы

В этой главе

• Мы продолжим изучение графов и познакомимся со взвешенными графами, в которых некоторым ребрам назначаются большие или меньшие веса.

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

• Вы узнаете о циклах в графах, для которых алгоритм Дейкстры не работает.

В предыдущей главе вы узнали, как найти путь из точки A в точку B.

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

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

Работа с алгоритмом Дейкстры

Посмотрим, как этот алгоритм работает с графом.

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

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

Этот путь занимает 7 минут. А может, существует путь, который займет меньше времени? Алгоритм Дейкстры состоит из четырех шагов:

1. Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).

2. Обновить стоимости соседей этого узла (вскоре я объясню, что имеется в виду).

3. Повторять, пока это не будет сделано для всех узлов графа.

4. Вычислить итоговый путь.

Шаг 1: найти узел с наименьшей стоимостью. Вы стоите в самом начале и думаете, куда направиться: к узлу A или к узлу B. Сколько времени понадобится, чтобы добраться до каждого из этих узлов?

До узла A вы будете добираться 6 минут, а до узла B — 2 минуты. Что касается остальных узлов, мы о них пока ничего не знаем.

Так как время достижения конечного узла остается неизвестным, мы считаем, что оно бесконечно (вскоре вы увидите почему.) Узел B — ближайший… он находится всего в 2 минутах.

Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех соседей B при переходе по ребру из B.

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

А если идти через узел B, то существует путь, который занимает всего 5 минут!

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

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

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

Шаг 3: повторяем!

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

Снова шаг 2: обновляем стоимости соседей A.

Путь до конечного узла теперь занимает всего 6 минут!

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

• Чтобы добраться до узла B, нужно 2 минуты.

• Чтобы добраться до узла A, нужно 5 минут.

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

Последний шаг — вычисление итогового пути — откладывается до следующего раздела. А пока я просто покажу, как выглядит итоговый путь.

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

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

На всякий случай повторим: алгоритм Дейкстры состоит из четырех шагов:

1. Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).

2. Проверить, существует ли более дешевый путь к соседям этого узла, и если существует, обновить их стоимости.

3. Повторять, пока это не будет сделано для всех узлов графа.

4. Вычислить итоговый путь (об этом в следующем разделе!).

Терминология

Я хочу привести еще несколько примеров применения алгоритма Дейкстры. Но сначала стоит немного разобраться с терминологией.