5.10. ЗАДАЧИ С ОДНИМ ИСТОЧНИКОМ

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

Для задач с одним источником мы не знаем объединяющего понятия, аналогичного замкнутым полукольцам и алгоритму 5.5. Если мы хотим только узнать, к каким узлам идут пути из источника, то задача тривиальна и ее можно решить несколькими алгоритмами, работающими времени на е-ребер ном графе. Так как алгоритм, если не "просматривает" все ребра, не может быть

Рис. 5.24, Алгоритм Дейкстры.

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

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

Алгоритм 5.6. Кратчайший путь из одного источника (алгоритм Дейкстры)

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

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

Метод. Строим такое множество что кратчайший путь из источника в каждый узел и целиком лежит в Массив содержит стоимость текущего кратчайшего пути из

Рис. 5.25. Граф с помеченными ребрами.

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

Пример 5.14. Рассмотрим граф, изображенный на рис. 5.25. Вначале для соответственно. При первой итерации цикла в строках 4—8 берем поскольку наименьшее значение для Затем вычисляем Последовательность значений для и другие вычисления алгоритма 5.6 приведены на рис. 5.26.

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

Доказательство, -цикл в строках 7, 8 требует шагов, столько же шагов требует и выбор в строке 5. В оценке сложности -цикла в строках 4—8 эти процессы преобладают над остальными, -цикл выполняется раз, так что общая его сложность равна Строки 1—3, очевидно, занимают времени.

Рис. 5.26. Вычисления алгоритма 5.6 на графе с рис. 5.25.

Рис. 5.27. Пути, идущие в узел и.

Чтобы показать корректность, надо доказать индукцией по размеру множества что для каждого ребра число равно длине кратчайшего пути из Более того, для всех число равно длине кратчайшего пути из лежащего целиком (если не считать сам узел

Базис. Пусть Кратчайший путь из в себя имеет длину О, а путь из в и, лежащий целиком (исключая состоит из единственного ребра Таким образом, строки 2 и 3 корректно формируют начальные значения массива

Шаг индукции. Пусть узел, выбранный в строке 5. Если число не равно длине кратчайшего пути из то должен быть более короткий путь Этот путь должен содержать некоторый узел, отличный от и не принадлежащий Пусть первый такой узел на Но тогда расстояние от до меньше а кратчайший путь в целиком (исключая сам узел лежит в (см. рис. 5.27). Следовательно, по предположению индукции в момент выбора пришли к противоречию. Отсюда заключаем, что такого пути нет и длина кратчайшего пути

Второе утверждение (о том, что остается корректным) очевидно ввиду строки 8.