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

Разбор известного алгоритма для начинающих с разбором моментов, с которыми я столкнулась. Приводится само объяснение работы алгоритма, без кода, чтобы лучше понимать саму суть. Да, поисковик выдаст 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; я написал и представил свою небольшую статью — мою вторую — в попытке помочь неоперившемуся [проекту]. Кроме того, синдром «публикуйся или пропадёшь!» [publish or perish] еще не достиг Нидерландов.

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

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

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

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

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

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

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

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

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

Ещё рано:) У нас есть ещё одна заметка под названием «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.

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

• Роттердам (1):

  • Отправная точка, вес = 0.

  • Пути:

    • До Утрехта (2) — 62 км.

    • До Амстердама (4) — 78 км.

  • Выбираем Утрехт как ближайшую вершину, перемещаемся туда.

    

• Утрехт (2):

  • Текущие расстояния:

    • До Утрехта — 62 км.

    • До Амстердама остаётся 78 км.

  • Пути:

    • До Арнема (3) через Утрехт — 127 км (62 + 65).

  • Переходим к Амстердаму (78 км < 127 км).

    

• Амстердам (4):

  • Текущие расстояния:

    • До Амстердама — 78 км.

  • Пути:

    • До Хорна (5) — 122 км (78 + 44).

    • До Дронтена (6) — 153 км (78 + 75).

  • Выбираем путь к Хорну.

  

• Хорн (5):

  • Текущие расстояния:

    • До Хорна — 122 км.

  • Пути:

    • До Дронтена — 190 км (оставляем 153 км).

    • До Херенвена — 233 км (122 + 111).

  • Переходим к Дронтену.

  • До Дронтена — 153 км.

    • Доступные пути из Дронтена:

      • До Зволле (7) — 184 км (153 + 31)

      • Переходим к Зволле.

        

• Зволле (6):

  • Текущие расстояния:

    • До Зволле — 184 км.

  • Пути из Зволле:

    • До Хогевена (8) — 231 км (184 + 47).

    • До Херенвена (9) — 248 км (184 + 64), однако ранее найденное минимальное расстояние до Херенвена — 233 км (через Хорн), поэтому не обновляем его.

    • Переходим к Хогевену.

    

• Хогевен (7):

  • Текущие расстояния:

    • До Хогевена — 231 км.

  • Доступные пути из Хогевена:

    • До Гронингена (10) — 295 км (231 + 64).

    • До Херенвена (8) — 295 (231 + 64). Но минимальное расстояние до Херенвена — (7,8) 233, поэтому переходим к Херенвену.

  

  Херенвен (8):

  • Текущие расстояния:

    • До Херенвена — 233 км.

  • Пути:

    • До Гронингена (10) — 294 км (233 + 61).

  • Расстояние до Гронингена через Херенвен (294 км) меньше, чем через Хогевен (295 км), поэтому обновляем минимальное расстояние до Гронингена.

  

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

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

Кратко

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

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

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

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

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

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

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

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

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

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

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

• Не подходит для графов с отрицательными весами рёбер.

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

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

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

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

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

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