«Едем» в Гронинген: длиннейшее описание поиска кратчайшего пути по следам Дейкстры, изобретателя известного алгоритма

Статья о том, что писал сам изобретатель Эдсгер Дейкстра о своём алгоритме поиска кратчайшего пути в первоисточнике. Приведён пример: как найти этот путь между двумя голландскими городами, которые посещал автор алгоритма.

Разбор известного алгоритма для начинающих с разбором моментов, с которыми я столкнулась. Приводится само объяснение работы алгоритма, без кода, чтобы лучше понимать саму суть. Да, поисковик выдаст 36 600 результатов при точном запросе. Но, возможно, кому‑то захочется знать историю вопроса и более неформального разбора. .

Как писал сам автор алгоритма:

«Слава богу, у нас есть не только серьёзные проблемы, но и нелепые». Э. В. Дейкстра

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

Однако название статьи, скорее всего, заинтересовало вопросом, что там за езда в Гронинген, поэтому на алгоритме и остановлюсь.

История появления алгоритма от Дейкстры

Поиск информации об алгоритме я решила начать с истоков вопроса. Просто стало интересно, при каких обстоятельствах, когда появилась эта идея и как выглядит первоисточник.

26-летний на тот момент ученый придумал алгоритм за 20 минут. (Очевидно, что такое не происходит «на пустом месте», для озарения должна быть «база».) Как Э. Дейкстра говорил в одном интервью, однажды он занимался шоппингом с невестой в Амстердаме, они сели выпить чашечку кофе, и ученому пришло решение. Сам он считал, что результат размышлений получился так хорош потому, что у него «не было карандаша и бумаги».

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

Учёный писал, что с момента «рождения» алгоритма при прогулке по Амстердаму до момента публикации статьи о нём прошло 3 года. Она случилась в 1959 году под названием «A note on two problems in connexion with graphs» («Заметка о двух проблемах, связанных с графами»). Тем не менее, идея остаётся актуальной десятилетия.

Если вы не интересовались первоисточником, вероятно, вам, как и мне раньше, представляется какая‑то брошюра с графическим объяснением процесса или даже с кодом. Однако документ занимает всего 2 страницы текста, набранного на печатной машинке, в котором нет кода и каких‑либо изображений.

Кстати, когда Дейкстре полагался секретарь по его должности, он предпочитал обходиться без него.

Заметка с описанием обстоятельств возникновения алгоритма

Под названием «A note on two problems in connexion with graphs» нашлось 2 документа: в одном не приводится никакого алгоритма, просто рассказывается, что такой путь был найден. (Мой перевод близко к тексту, в квадратных скобках [ ] указываю свои примечания.)

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

Задача 1. Построить дерево минимальной суммарной длины между n вершинами.
Задача 2. Найти путь минимальной суммарной длины между двумя заданными вершинами.

Я нашел свое решение второй проблемы в 1956 году после создания первой. В то время я был главным программистом Математического центра в Амстердаме, где близилась к завершению конструкция его второго автоматического компьютера, и для празднования его открытия нам нужна была красивая демонстрация: он должен решать задачу, которая может быть легко изложена для преимущественно непрофессиональной аудитории. Для демонстрации я нарисовал немного упрощенную карту голландской железнодорожной системы, кто-нибудь из зрителей мог спросить о кратчайшем пути, скажем, между Харлингеном и Маастрихтом, и ARMAC распечатывал этот кратчайший маршрут город за городом. Демонстрация прошла с большим успехом; я помню, что мог показать, что перемена мест исходного пункта и пункта назначения может повлиять на требуемое время вычислений. Скорость ARMAC и размер карты были такими, что всегда хватало одной минуты.

Я нашел решение первой проблемы примерно через год, когда строилась следующая [вычислительная] машина, и меня спросили, могу ли я минимизировать количество кабеля, необходимого для строительства, и меня спросили, могу ли я минимизировать количество кабеля, необходимого для монтажа на объединительной плате, который должен был соединить штифты древовидного дешифратора. Это открытие [автор имеет в виду проблему номер 1, нахождение дерева минимальной длины] я помню ярче, чем открытие самого короткого маршрута [проблемы номер 2]: мы с женой пили кофе перед каким-то кафе на солнечной стороне Дамрака. Я нашел оба решения без таких вспомогательных средств, как карандаш и бумага. Очевидно, это была более интересная из двух задач: глядя на то, как моя программа представляет деревья, я заново открыл теорему Кэли* о том, что число различных деревьев, соединяющих n вершин, равно n в степени (n-2) (с доказательством того, что намного лучше, чем оригинал Кэли).

В то время я полностью осознавал, что нашел две жемчужины: в момент открытия я был должным образом взволнован и помню, что представил их на лекции. Оглядываясь назад, кажется странным, что я ждал еще два года, прежде чем представить их для публикации. Главной причиной было отсутствие журналов, посвященных автоматическим вычислениям, что и пытались исправить основанием [журнала] Numerische Mathematik; я написал и представил свою небольшую статью — мою вторую — в попытке помочь неоперившемуся [проекту]. Кроме того, синдром «публикуй или погибни!» еще не достиг Нидерландов.

Решения, столь же элегантные, сколь и эффективные, теперь принадлежат интеллектуальному багажу любого хорошо образованного ученого-компьютерщика, и тот, кто первым опубликует их, получит признание и «соберет» ссылки. Я рад видеть, что к настоящему времени компьютерное сообщество начинает рассматривать их как «общее достояние» и обращаться к ним, не упоминая моего имени: их рождение стало историей (как и должно быть).

Э. В. Дейкстра «Заметка о двух проблемах, связанных с графами», 1 версия.

Но имя учёного стали упоминать практически сразу же: по его собственному признанию, он нашёл первую отсылку к своему труду в немецком издании по менеджменту в начале 60-х под названием «Das Dijkstra»sche Verfahren» (метод Дейкстры).

А упомянутый в статье выше автором Дамрак — это улица в Амстердаме, «местная Уолл‑стрит», которая в 1950-х годах выглядела так.

По признанию автора алгоритма в одном из интервью (Dijkstra (2001), in an interview with Philip L. Frana), он опубликовал его не в 1956, а позднее, в 1959 по следующим соображениям.

«В то время что‑то вроде алгоритма кратчайшего пути вряд ли могло считаться математикой: было конечное число способов попасть из [точки] А в [точку] Б и, очевидно, среди них был самый короткий, так ради чего вся эта суета?» Э. В. Дейкстра.

Но когда к учёному обратился основатель журнала Numerische Mathematik, первый вспомнил, что находил практическое применение своего решения на работе для своих друзей, занимающихся аппаратным обеспечением. На большой панели нужно было подключить много контактов, чтобы было одинаковое напряжение (о чём и было сказано в первой статье, приведённой выше). Стояла задача минимизировать количество провода.

Волна интереса к алгоритму Дейкстры поднялась снова в связи с технологиями GPS‑навигации. Сам автор статьи удивился тому, что в 2000 году офтальмолог на приёме узнал его благодаря двухмесячной на тот момент статье в журнале Scientific American, смысл названия которой: «Атлант расправил плечи. Почему вы не можете (стабильно) добираться из одного места в другое, когда речь заходит об онлайн‑картах».

Где изучается алгоритм

В рамках дисциплины под названием теория графов. Она кажется пугающе абстрактной, но у неё есть вполне конкретные «точки приложения» в реальных задачах. Когда мы говорим о графах, то рассматриваем вершины (узлы, точки) и рёбра (связи, линии, дуги).

G = (V, E), где G — граф, V — множество вершин, E — множество рёбер.

Теория графов изучает то, что называется по‑английски relations (отношения, взаимосвязи) между объектами.

Э. Дейкстру, помимо решения иных задач, интересовал и поиск кратчайшего пути в физическом мире между населенными пунктами. Если вспомнить зарождение идеи графов, то Эйлера тоже интересовала вполне конкретная задача: можно ли придумать такой маршрут, который не пролегал бы через один и тот же остров дважды. Вместо этих двух городов могут быть другие объекты.

Что бы ни было в качестве вершин (города, мосты или другие данные), то, чем занимается алгоритм Дейкстры, относится к алгоритмам поиска кратчайшего пути из одного источника SSSP (Single Source Shortest Path).

В каких графах можно применять алгоритм Дейкстры

Для использования алгоритма Дейкстры важно учесть несколько условий.

Взвешенный или невзвешенный граф?

В невзвешенных графах ребра считаются равноценными. Однако иногда у каждого ребра может быть параметр: длина или стоимость, которая называется весом графа. Алгоритм применяется именно для взвешенных графов (weighted graph). Графически это обозначается числами около ребер, но в коде удобна матрица смежности или связанные списки.

С положительными или отрицательными весами?

У алгоритма Дейкстры есть ещё одна особенность, сразу заявленная автором: он не используется там, где могут быть отрицательные веса рёбер графа. Стоит отметить, что он может иногда сработать, если используются отрицательные веса, но если в случае с положительными значениями работа алгоритма гарантируется, то в случае с отрицательными будут ошибки. Поэтому для этих случаев используются другие подходы.

Так как в качестве примеров из реального мира мы упоминали расстояния, может показаться неестественным, что ребро может иметь отрицательный вес. Однако веса ребер могут оказаться отрицательными, например, при построении модели получения максимальной прибыли при валютных спекуляциях.

Ориентированный или неориентированный граф?

Графы есть ориентированные (сокращённо: орграфы) и неориентированные (неорграфы). Несложно догадаться, что в первом случае ребрам присвоено направление. Во втором случае направление не задаётся. Если есть направление, ребро ориентировано, тогда оно называется дугой. Графически обозначается стрелками. В матрице рассматриваем строки: если из вершины выходит ребро, то ставим 1 (для графов без веса) или вес для взвешенных графов. Когда рассматриваем столбцы — то смотрим на рёбра, которые входят.

Алгоритм Дейкстры работает в ориентированном графе так же, как и в неориентированном, если нет рёбер с отрицательным весом.

Связные и несвязные граф?

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

Жадный алгоритм или ещё какой-нибудь?

Помимо этого, про алгоритм Дейкстры часто можно услышать, что его относят к так называемым жадным алгоритмам (greedy).

Вспомним, в чем заключается для алгоритмов «корысть»:

• на каждом этапе выбирается лучшее только на данный момент решение;

• не интересует общий оптимальный результат;

• никогда не отменяется предыдущее решение, даже если выбор был неверен.

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

Как‑то мне попался вопрос насчёт того, почему алгоритм «жадный», если он ищет оптимальный путь, а не «жадно хватает много». Дело в том, что алгоритм — именно жадный, а не «голодный»:) Может показаться, что жадность заключается в свойстве «схватить как можно больше», на самом деле это свойство проще представлять как способность «потратить как можно меньше на данном шаге».

Алгоритм «не задумывается» о том, приведёт ли это «скупердяйство» к наименее затратному пути в целом.

Какие есть ещё ограничения?

Некоторые отмечают, что алгоритм легко применять к небольшому графу, что касается большого графа, то имеются проблемы с вычислением.

Что ещё можно сказать об алгоритме?

Алгоритм использует так называемую операцию релаксации (relaxation) или ослабления. Это можно представить как ослабление ограничения на кратчайший путь. Как алгоритм из одного истока, он использует релаксацию ребра.

Что с алгоритмом?

Ещё рано:) У нас есть ещё одна заметка под названием «A note on two problems in connexion with graphs», но в Numerische Mathematik, и в ней уже есть описание алгоритма, но занимает она так же 2 страницы. Журнал выходит до сих пор, алгоритм Дейкстры был написан в самом первом номере.

Что написано в оригинале? Если ещё не читали, то вот перевод, сохраняю близко к оригиналу, в квадратных скобках [ ] указываю свои примечания.

Рассмотрим точки (вершины) [примечание: или узлы], некоторые или все пары которых соединены ветвями, указана длина каждой ветви. Ограничимся случаем, где существует, по крайней мере, один путь между любыми двумя вершинами. Сейчас мы рассматриваем две проблемы.

Проблема 1. Постройте дерево минимальной суммарной длины между n вершинами. (Дерево — это граф с одним и только одним путём между каждыми двумя узлами.)

• В ходе конструкции, которую мы здесь представляем, ответвления подразделяются на три группы:

• I. Ответвления, обязательно назначаемые строящемуся дереву (они будут сформировывать поддерево).

• II. Ответвления, из которых будет выбрана следующая ветвь и будет добавлена к множеству I.

• III. Оставшиеся ответвления (отклонённые или ещё не рассмотренные).

Вершины подразделяются на два набора:

• A. Вершины, соединённые ветвями множества I.

• B. Остальные вершины (к каждому из этих узлов будет вести одна и только одна ветвь множества II).

Начнём построение с выбора произвольной вершины в качестве единственного элемента множества A, и поместив все ветви, которые заканчиваются в этой вершине, во множество II. Начнём с того, что множество I пусто. С этого момента мы выполняем следующие два шага несколько раз.

Шаг 1. Кратчайшая ветвь множества II удаляется из этого множества и добавляется к множеству I. В результате одна вершина переносится из множества B во множество I.

Шаг 2. Рассмотрим ветви, идущие от вершины, что только что были перенесены во множество А, к вершинам, ещё находящимся во множестве B. Если рассматриваемая ветвь длиннее соответствующей ветви во множестве II, она отбрасывается, если короче — заменяет соответствующую ветвь во множестве II, и позже — отбрасывается.

Затем мы возвращаемся к шагу I и повторяем процесс до тех пор, пока наборы II и B не опустеют. Ветки во множестве образуют необходимое дерево.

Приведённое здесь решение следует предпочесть решениям, данному Дж. Б. Краскелом и предоставленным Г. Лоберманом и А. Вейнбергом. В их решении все возможные ½ n (n — 1) ответвления сортируются, в первую очередь, по длине. Даже если длина ветвей — вычислимая функция координат узла, из методы требуют, чтобы данные для всех ветвей хранились одновременно. Наш метод требует одновременного хранения данных не более чем для n ветвей, а именно: ветвей во множествах I и II и ветви, рассматриваемой на Шаге 2.

Проблема 2. Найдите минимальную общую длину пути между двумя заданными вершинами P и Q. Воспользуемся тем, что если R — вершина на минимальном пути из P в Q, то знание последнего [значения Q] подразумевает знание минимального пути из P в R. В представленном решении минимальные пути от P к другим вершинам строятся в порядке возрастания длины, пока не будет достигнуто Q.

По ходу решения вершины подразделяются на три множества:

• A. Вершины, для которых известна минимальная длина пути из P; вершины будут добавлены в этот набор в порядке увеличения минимальной длины пути от вершины P.

• B. Вершины, из которых будет выбрана следующая вершина, добавляемая в набор А; это множество включает в себя все те узлы, которые связаны хотя бы с одним узлом множества А, но сами еще не принадлежат А.

• C. Остальные узлы.

Ветви также подразделяются на 3 группы:

• I. Ответвления, встречающиеся на минимальных путях от вершины P к вершинам множества A.

• II. Ответвления, из которых я буду выбирать следующую ветвь для помещения в набор. Одна и только одна ветвь этого множества будет вести к каждой вершине множества B.

• III. Остальные ответвления (отклонённые или ещё не рассмотренные).

Начнём с того, что все узлы находятся во множестве C, а все ветви — в наборе III. Теперь мы переносим узел P в множество A и с этого момента многократно выполняем следующие шаги.

Шаг 1. Рассмотрим все ветви r, соединяющие только что перенесённый узел в множество A с узлами R в множествах B или C.

Если узел R принадлежит множеству B, мы исследуем, использование ветви r приводит к более короткому пути от P к R, чем известный путь, который использует соответствующую ветвь в множестве II. Если, однако, использование ветви r устанавливает более короткое расстояние между P и R, чем полученное до этого, она заменяет соответствующую ветвь в множестве II, и последняя отбрасывается.

Если узел R принадлежит множеству C, он добавляется к множеству B, а ветвь r добавляется к множеству II.

Шаг 2. Каждый узел во множестве B может быть соединен с узлом P только одним способом, если мы ограничимся ветвями из множества I и одной из множества II. В этом смысле каждый узел в множестве B имеет расстояние от узла P: узел с минимальным расстоянием от P переносится из множества B в множество A, а соответствующая ветвь переносится из множества II в множество I. Затем мы возвращаемся к шагу I и повторяем процесс до тех пор, пока узел Q не будет перенесен в множество A. Тогда решение найдено.

Замечание 1. Описанный выше процесс может быть применён и в том случае, когда длина ветви зависит от направления, в котором она проходит [в ориентированном графе, то есть].

Замечание 2. Для каждой ветви в множествах I и II целесообразно записывать две её вершины (в порядке увеличения расстояния от P) и расстояние между P и той вершиной ветви, которая наиболее удалена от P. Для ветвей множества I это фактическое минимальное расстояние, для ветвей множества II это только достигнутый к настоящему времени минимум.

Приведённое выше решение следует предпочесть решению Л. Р. Форда, описанному К. Берге, поскольку, независимо от числа ветвей, нам нужно хранить данные не для всех ветвей одновременно, а только для ветвей в множествах I и I, II, и это число всегда меньше n. Кроме того, объем работы, который необходимо выполнить, кажется, значительно меньше.

Э. В. Дейкстра «Заметка о двух проблемах, связанных с графами», 2 версия.

Немного о местности, где мы будем «строить граф»

Демонстрация алгоритма его автором упоминалась ещё и в рамках проектирования и карты между 64 населёнными пунктами Нидерландов для показа аудитории.

Но мы будем рассматривать путешествие из Петербурга в Москву из Роттердама в Гронинген, так же упомянутое как пример Э. Дейкстрой в одном из интервью. Воспользуемся современной картой местности, чтобы быстрее вычислить расстояния между нужными объектами.

Кстати говоря, за 3 года до изобретения алгоритма, Нидерланды пережили крупнейший за 400 лет потоп. Предполагалась, что «хитроумная система дамб» может вынести любой шторм, но зимой 1953 ветры на скорости больше 150 км в час обрушили воды Северного моря на жилища.

Были попытки присвоить катастрофе безобидные названия вроде «наводнение Святого Игнатия». Однако в историю это вошло как «катастрофа 1953 года». Многие населённые пункты, включая Роттердам, были затоплены.

Описание использования алгоритма Дейкстры

Можно убедиться, что от Роттердама до Гронингена по меркам Нидерландов (по сравнению с Россией) далеко: почти 250 км через всю страну. Гугл Карта показывает самый короткий маршрут 13+ часов езды на велосипеде.

Представим, что у нас, как у Эдсгера В. Дейкстры в 1956, нет «умного Гугла», и нам нужно найти кратчайший путь: через какие населенные пункты ехать, чтобы быстрее добраться до нужного города. Думаю, дорожная система претерпела с той поры изменения, однако, это нисколько не помешает нам разобраться в проблеме.

Задача: найдем кратчайшее расстояние от Роттердама до Гронингена. А также заодно кратчайшие расстояния до других городов, которых мы отобрали для своего пути.

Я выберу некоторые населённые пункты в качестве вершин графа, в качестве весов рёбер можно взять расстояние или затрачиваемое на транспорте (или пешком) время.

А можно было в качестве весов взять не расстояние, а какую‑то стоимость проезда или оценку «неудовольствия» посещения городов! Можно ставить оценки городам исходя их желания их посетить: для более желаемых низкая оценка, а городам, где уже были — более высокие веса. Всё потому, что графы — это абстрактные структуры.

Для того чтобы никого не путать, я возьму расстояние между пунктами. В нарисованном маршруте пока нет никакой идеи, я просто показала, какие населённые пункты я беру для нашей задачи. Затем я буду смотреть: сколько километров по дороге, где может проехать автомобиль, от одного населённого пункта до другого.

Выпишу населенные пункты — вершины графа:

1. Роттердам.

2. Утрехт.

3. Арнем.

4. Амстердам.

5. Хорн.

6. Херенвен.

7. Зволле.

8. Хогевен.

9. Дронтен.

10. Гронинген.

Для того чтобы указать веса рёбер, я возьму следующие расстояния (расстояния примерные, реальные километры нам неважны):

1. Роттердам — Амстердам: 78 км.

2. Роттердам — Утрехт: 62 км.

3. Утрехт — Арнем: 65 км.

4. Амстердам — Хорн: 44 км.

5. Хорн — Херенвен: 111 км.

6. Херенвен — Гронинген: 61 км.

7. Амстердам — Дронтен: 75 км.

8. Арнем — Дронтен: 82 км.

9. Арнем — Зволле: 69 км.

10. Дронтен — Зволле: 31 км.

11. Хорн — Дронтен: 68 км.

12. Херенвен — Зволле: 64 км.

13. Зволле — Хогевен: 47 км.

14. Хогевен — Херенвен: 64 км.

15. Хогевен — Гронинген: 64 км.

Отмечу на карте вершины графа числами, рёбра графа и их веса (расстояние в километрах по автомобильным дорогам в нашем случае). Граф неориентированный, чтобы не усложнять.

Найдём кратчайшее расстояние от вершины 1 до всех вершин графа. В начальной точке вес равен 0, потому что мы ниоткуда ещё «не выехали» и никакого расстояния «не проехали». Непосещённые вершины обозначаются обычно знаком «бесконечность» ∞ (т. к. ещё не известно расстояние до них), не будем отходить от этого правила.

Мы выдвигаемся из Роттердама (1) и перед нами две дороги (рёбра графа): в Амстердам (4) и Утрехт (2). Находясь в пункте 1 мы знаем, что по дороге в Амстердам мы будем ехать 78 км, а до Утрехта 62 км. До Утрехта быстрее, поэтому едем туда. Записываем себе в блокнот, что мы выехали из Роттердама, чтобы туда не возвращаться. Записываем также, что от начального пункта до Роттердама: (1, 4) 78 км; а до Утрехта 62 км: (1, 2) 62.

Серая стрелка — возможный путь, по которому мы не поехали, но до которого посчитали суммарное расстояние от точки 1.

Стрелка цвета фуксии — выбранный путь с минимальным возможным расстоянием, который оценивается в каждой вершине.

Вершина 1 соединена:

• с вершиной 2: вес ребра 62;

• с вершиной 4: вес ребра 78.

62 < 78, поэтому переходим к вершине 2, вершину 1 помечаем как пройденную. Запоминаем, вес ребра (1, 4) 78 и (1, 2) 62.

В Утрехте мы можем даже не останавливаться, так как проехали всего 62 км и нам не нужно выбирать следующий город, он только один — Арнем (3). Помечаем вершину 2 как пройденную, записываем, что дорога от Роттердама до Арнема через Утрехт займёт 127 км: (2,3) 127.

Через 65 км приезжаем в Арнем и снова встаём перед выбором: по какой дороге ехать. Мы знаем, что до Дронтена (5) — 82 км, а до Зволле (6) — 69 км.

Очевидно, что для выбора кратчайшего пути нужно сложить путь, который мы проехали, и планируемый путь до следующих пунктов и сравнить их.

127 км от Роттердама через Утрехт до Арнема. До Дронтена будет 82+127= 291 км. До Зволле быстрее — 69 + 127 = 196 км. Отмечаем так же, что пока других сведений о других путях в эти города нет (знак бесконечности). Поэтому выбираем: 291 > 196, отправляемся в Зволле!

Мы находимся в 6-й вершине, пришли туда из 3-ей с суммарным весом 196: (3, 6) 196.

В Зволле (6) мы можем выбрать целых 3 пути: в Херенвен (8), в Хогевен (9) и в Дронтен (5).

Здесь нужно проявить внимательность. У нас уже записан суммарный вес (1–2–3–5) 209 для вершины 5.

Считаем, до чего добраться быстрее:

• Хогевен: 196 км + 47 км = 243 км.

• Херенвен: 196 км + 64 км = 260 км.

• Дронтен: 196 км + 31 км = 227 км.

Вспоминаем, что до Дронтена (5) добраться быстрее другим путём, 209 км < 227 км и меньше остальных расстояний, поэтому перемещаемся в вершину 5.

Возможно, тут будет некоторое непонимание, что происходит. Да, для поиска оптимального результата мы «проехали» больше, чем указано в вершине 5, где мы сейчас находимся, т. к. мы не знали сразу, что путь 1–2–3–5 кратчайший, мы посетили вершины 1–2–3–6–5. Это нормально для алгоритма Дейкстры (посещать все вершины).

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

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

От Дронтена идут две дороги (вершина 5 соединена с вершиной 4 и 7 рёбрами). От Дронтена до Амстердама (4) 75 км, до Хорна (7) — 68.

Обращаем внимание, что в вершине 4 уже есть пометка, что вес ребра (1,4) 78. 284 > 78, поэтому оставляем это значение.

От Роттердама через Амстердам до Дронтена 78 + 75 = 153. 153 < 209, поэтому заменяем информацию по вершине 5: (4, 5) 153.

От Дронтена до Хорна с учётом новых данных 153 + 68 = 221.

В Амстердаме у нас один путь — до Хорна. На предыдущем шаге мы считали общий путь через вершину 5: 221. Но теперь мы понимаем, что через вершину 4 (78+44=122) добраться «дешевле». Заменяем эту информацию для вершины 7: (4, 7) 122.

Из Хорна (7) мы можем попасть в Херенвен (8), наш путь составит 233. Нужно проверить прежнюю информацию — путь через Зволле занял бы 260 км. Мы ищем кратчайший, поэтому заменяем эту информацию на 233.

Из Херенвена (8) у нас 2 пути: в Гронинген (10) и Хогенвен (9). В вершине 10 у нас нет никакой информации о суммарном пути, поэтому считаем 233 + 61 = 294. В Хогевен (8) мы уже просчитали путь из Зволле (6), он равнялся 243. Если наш путь пройдет через Херенвен, то в лучшем случае мы проедем 233 + 64 = 297.

Так как в нашей задаче стояло найти кратчайшие пути до всех населённых пунктов, а не только до Гронингена, то посетим оставшийся Хогевен.

Путь через Гронинген (10) до Хогевена (9) займет 294 + 64 = 358. Через Зволле (6) туда попасть гораздо быстрее — 243. Поэтому информацию для вершины 9 не обновляем.

Результат работы алгоритма

Нашу виртуальную «поездку», она же работа алгоритма, мы проделывали ради того, чтобы получить на будущее информацию о том, как быстрее ездить между городами. Если говорить о графе, то мы получили информацию о кратчайших путях от заданной вершины графа до остальных. Представим это на карте.

Для начала посмотрим, какой путь мы проделали, чтобы выяснить самый короткое расстояние от вершины 1 до каждой.

Кратчайшие маршруты к каждому населенному пункту выглядят так.

Самый короткий путь из Роттердама в Гронинген выглядит так, как указаено ниже. Это значит, что мы можем пользоваться результатом работы алгоритма, когда нам понадобится добраться из вершины 1 в вершину 10 с минимальными потерями.

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

Кратко

• Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути в графе:

  • ориентированном или неориентированном;

  • взвешенном;

  • без отрицательных весов.

• Относится к алгоритмам поиска кратчайшего пути из одного источника (SSSP).

• Алгоритм выбирает вершину с минимальным известным расстоянием от источника в каждом шаге.  Это ключевая часть работы алгоритма.

• Алгоритм предполагает поиск кратчайшего пути от конкретной вершины до всех остальных вершин.

• Считается «жадным».

• Для больших графов применяют оптимизации, делая алгоритм более применимым к большим графам.

• Среди плюсов алгоритма — сравнительно низкая сложность.

• Не лучший вариант, если граф плотный (у многих пар вершин есть рёбра между ними).

Какие могут быть проблемы при применении

Проблемы с алгоритмом Дейкстры: когда можно «запутаться»

Вот некоторые ситуации, где можно ошибиться:

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

2. Вершины с одинаковым расстоянием. Представьте, что у вас есть несколько путей до одной и той же точки, и все они одинаковые. Алгоритм не «тревожится» по этому поводу. Обычно алгоритм использует порядок, в котором точки были добавлены в очередь на обработку, если не указано другого.

3. Алгоритм «обходит» не все вершины? Проверьте, связный ли граф (можно добраться из любой вершины в любую другую вершину по ребрам). Если вы хотите «просканировать» весь несвязный граф, то вам нужно «запустить» алгоритм из разных начальных точек, покрывающих все «острова». Или превратить граф в связный, но это изменит его структуру.

Важно: Чтобы ваш алгоритм работал правильно, нужно убедиться, что все допустимые пути проверяются, а расстояния до всех доступных вершин обновляются.