Шпаргалка
• Поиск в ширину позволяет определить, существует ли путь из A в B.
• Если путь существует, то поиск в ширину находит кратчайший путь.
• Если в вашей задаче требуется найти «кратчайшее X», попробуйте смоделировать свою задачу графом и воспользуйтесь поиском в ширину для ее решения.
• В направленном графе есть стрелки, а отношения действуют в направлении стрелки (Рама —> Адит означает «Рама должен Адиту»).
• В ненаправленных графах стрелок нет, а отношение идет в обе стороны (Росс – Рэйчел означает «Росс встречается с Рэйчел, а Рэйчел встречается с Россом».)
• Очереди относятся к категории FIFO («первым вошел, первым вышел»).
• Стек относится к категории LIFO («последним пришел, первым вышел»).
• Людей следует проверять в порядке их добавления в список поиска, поэтому список поиска должен быть оформлен в виде очереди, иначе найденный путь не будет кратчайшим.
• Позаботьтесь о том, чтобы уже проверенный человек не проверялся заново, иначе может возникнуть бесконечный цикл.
7. Алгоритм Дейкстры
В этой главе
• Мы продолжим изучение графов и познакомимся со взвешенными графами, в которых некоторым ребрам назначаются большие или меньшие веса.
• Вы изучите алгоритм Дейкстры, который позволяет получить ответ на вопрос «Как выглядит кратчайший путь к 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.