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

Рассмотрим следующую карту:

Рис. 10.3. Каков кратчайший маршрут между городами 1 и 5?

Алгоритм Дейкстры предполагает, что я начинаю путешествие из начального города, города 1. На каждом этапе я буду вычислять для каждого города промежуточную сумму расстояний, что должно помочь мне найти кратчайший маршрут. Первым делом я помечу все города, связанные с начальным, расстояниями до них. В данном случае города 2, 3 и 6 получают соответственно метки 7, 9 и 14, и первым ходом я перемещаюсь в ближайший из этих городов. Однако следует помнить, что, когда алгоритм чудесным образом решит задачу, может оказаться, что самым лучшим первым ходом был переезд совсем в другой город.

Итак, вначале я переезжаю в город 2, потому что он расположен на самом малом расстоянии от начального пункта, города 1.

Затем я присваиваю городу 1, из которого я только что уехал, метку «посещенного». Находясь в следующем пункте, городе 2, я должен изменить метки всех городов, связанных с ним. Следовательно, речь идет о городах 3 и 4. Сначала я вычисляю расстояние до них от исходного пункта, города 1, через тот пункт, в котором я нахожусь, город 2. Если новое расстояние короче, чем то, которым следующий город помечен сейчас, я присваиваю ему метку с новым расстоянием. Если новое расстояние больше, город сохраняет старую метку. В случае города 3 новое расстояние (7 + 10) больше старого; следовательно, у этого города остается старая метка с числом 9. У некоторых городов, например города 4, может не быть предыдущей метки, потому что они не связаны с городами, которые я посетил до этого. Теперь я присваиваю этим новым городам метки с только что вычисленными расстояниями до них. Таким образом, город 4 получает метку с числом 7 + 15 = 22.

Теперь я снова помечаю город, в котором я нахожусь, как посещенный и переезжаю в следующий город, имеющий самую малую текущую сумму расстояний от начального пункта. В результате описанных выше операций таким пунктом оказывается город 3. В этом примере видно, что, хотя первое перемещение в город 2 казалось рациональным, дальнейший путь из него оказывается не самым коротким. Поэтому уже на этом этапе алгоритм может склоняться к прокладке маршрута через город 3.