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

Наиболее быстрым из известных в настоящий момент алгоритмов поиска минимального остова (для случая \Е\ = Q(VlgV)) является алгоритм Прима, реализованный с помощью фибоначчиевой кучи. Для более разреженных графов Фредман и Тарьян [75] приводят алгоритм, время работы которого составляет 0(Е(3(\Е\, \V\)), где (3(\E\,\V\) = mm{i : lgW\V\ \E\/\V\}. Поскольку \E\ \V\, время работы этого алгоритма есть 0(E\g* V).

Кратчайшие пути из одной вершины

Перед нами - карта автомобильных дорог США с обозначенными расстояниями; как выбрать кратчайший маршрут от Чикаго до Бостона?

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

В этой и следующей главах мы рассказываем о том, как можно эффективно решать такие задачи. В задаче о кратчайшем пути (shortest-paths problem) нам дан ориентированный взвешенный граф G = (V, Е) с вещественной весовой функцией w: Е -> Ж. Весом (weight) пути р = (г>о, v\,..., vk) называется сумма весов рёбер, входящих в этот путь:

Вес кратчайшего пути (shortest-path weight) из и в v равен, по определению,

Кратчайший путь (shortest path) из и в v - это любой путь р из и в v, для которого w(p) = 5(и, v).

В нашем примере с Чикаго и Бостоном можно рассматривать карту дорог как граф, вершинами которого являются перекрёстки, а рёбрами - участки дорог между ними. Вес ребра - это длина участка дороги, и наша задача может состоять в отыскании кратчайшего пути между данным перекрёстком в Чикаго и данным перекрёстком в Бостоне.

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

к

г=1

min{w(p) : и и}, если существует путь из и в и;

иначе.

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

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

Варианты задачи о кратчайшем пути

В этой главе мы рассматриваем только задачу о кратчайших путях из одной вершины (single-source shortest-path problem): дан взвешенный граф G = (V, Е) и начальная вершина v (source vertex); требуется найти кратчайшие пути из s во все вершины v £ V. Алгоритм, решающий эту задачу, пригоден и для многих других задач, например:

Кратчайшие пути в одну вершину: дана конечная вершина t (destination vertex), требуется найти кратчайшие пути в t из всех вершин v £ V. (В самом деле, если обратить все стрелки на рёбрах, эта задача сведется к задаче о кратчайших путях из одной вершины.)

Кратчайший путь между данной парой вершин: даны вершины и и v, найти кратчайший путь из и в v. Разумеется, если мы найдем все кратчайшие пути из и, то тем самым решим и эту задачу; как ни странно, более быстрого способа (который бы использовал тот факт, что нас интересует путь лишь в одну вершину) не найдено.

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

Рёбра отрицательного веса

В некоторых приложениях веса рёбер могут быть отрицательными. При этом важно, есть ли циклы отрицательного веса. Если из вершины из s можно добраться до цикла отрицательного веса, то потом можно обходить этот цикл сколь угодно долго, и вес будет всё уменьшаться, так что для вершин этого цикла кратчайших путей не существует (рис. 25.1). В таком случае мы будем считать, что вес кратчайшего пути есть -оо.

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

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