Глава 21. Кратчайшие пути. Для обозначения общего метода получения V проходов по ребрам с просмотром ре­бер в любом порядке мы будем использовать термин алгоритм Белпмана-Форда

Для обозначения общего метода получения V проходов по ребрам с просмотром ре­бер в любом порядке мы будем использовать термин алгоритм Белпмана-Форда. Некото­рые авторы применяют этот термин для описания более общего метода (см. упражнение 21.130).

Например, для графа, представленного списками смежных вершин, алгоритм Беллма-на-Форда поиска кратчайших путей из стартовой вершины s реализуется с помощью ини­циализации элементов wt значениями, большими, чем любая длина пути, и элементов spt — нулевыми указателями, и затем в соответствие с кодом, показанным ниже:

wt[s] = 0;

for (i = 0; i < G-> V(); i++) for (v as 0; v < G-> V(); v++) {

if (v! = s & & spt[v] == 0) continue; typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) if (wt[e-> w()] > wt[v] + e-> wt())

{ wt[e-> w()] = wt[v] + e-> wt(); st[e-> w()] = e; } }

Этот код демонстрирует простоту базового метода. Однако на практике он не исполь­зуется из-за того, что простые модификации, как вскоре будет показано, дают реализа­ции, которые являются более эффективными для большинства графов.

Свойство 21.21. С помощью алгоритма Беллмана-Форда можно решить задачу поис­ка кратчайшего пути для единственного источника в сетях, не содержащих отрицатель­ных циклов, за время, пропорциональное VE.

Доказательство: Мы делаем V проходов через все Е ребер, так что полное время бу­дет пропорционально VE. Чтобы доказать, что это вычисление достигнет желаемого результата, методом индукции по i мы показываем, что, для всех вершин v, после /-того прохода wt[v] оказывается не больше, чем длина кратчайшего пути из s в v, ко­торый содержит i или менее ребер. Утверждение несомненно истинно для i равного 0. Полагая, что требование истинно для i, рассмотрим два возможных случая для каж­дой данной вершины v. Среди путей из s в v с i + 1 или меньшим количеством ребер там либо может, либо не может существовать кратчайший путь с i + 1 ребрами. Если наиболее короткий из путей с i + 1 или меньше ребрами из s в v имеет длину / или меньше, то wt[v] не будет изменяться и останется допустимым. В противном случае, существует путь из s в v с i + 1 ребрами, более короткий, чем любой путь из s в v с / или менее ребрами. Этот путь должен сложиться из пути с / ребрами из s в некоторую вершину w плюс ребро w-v. По предположению индукции, wt[w] суть верхняя грани­ца на наиболее коротком расстоянии из s в w, и (i+1)-й проход проверяет каждое реб­ро, является ли оно конечным ребром в новом кратчайшем пути к адресату этого реб­ра. В частности, проверяется ребро w-v.

После V- 1 итераций wt[v] определяет нижнюю границу длины любого кратчайшего пути с V- 1 или менее ребрами, ведущего из s в v, для всех вершин v. Мы можем ос­тановиться после V— 1 итераций из-за того, что любой путь с Кили более ребрами дол­жен содержать цикл (с положительной или нулевой стоимостью) и за счет удаления этого цикла мы могли бы отыскать путь с V— 1 или менее ребрами, который имеет ту же длину или является более коротким. Поскольку wt[v] есть длина некоторого пути

Часть 5. Алгоритмы на графах

из s в v, это значение является также верхней границей длины кратчайшего пути, и та­ким образом, должно быть равно длине кратчайшего пути.

Хотя это и не рассматривалось явно, то же самое доказательство показывает, что век­тор spt содержит указатели на ребра в дереве кратчайших путей с корнем в s. ■

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

Программа 21.9. Алгоритм Беллмана-Форда___________________________________

Эта реализация алгоритма Беллмана-Форда поддерживает очередь FIFO всех вершин, для которых ослабление вдоль исходящего ребра могло бы оказаться эффективным. Мы берем вершину из очереди и производим ослабление вдоль всех ее ребер. Если любое из них приводит к более короткому пути в некоторую вершину, мы помещаем ее в очередь. Сигнальное значение G-> V отделяет текущую серию вершин (которые изменились на последней итерации) от следующей серии (которые изменятся на данной итерации) и позволяет остановиться после прохода G-> V.

SPT (Graph & G, int s): G(G),

spt(G.VO), wt(G.V(), G.V()) { QUEUE< int> Q; int N = 0; wt[s] - 0.0; Q.put(s); Q.put(G.VO); while OQ.emptyO) { int v;

while ((v = Q.getO) == G.v())

{ if (N++ > G.V()) return; Q.put(G.V()); } typename Graph:: adjIterator A(G, v); for (Edge* e = A.beg();! A.end(); e = A.nxt()) { int w = e-> w(); double P = wt[v] + e-> wt(); if (P < wt[w])

{ wt[w] = P; Q.put(w); spt[w] = e; } } } }

Программа 21.9 является прямой реализацией с использованием очереди FIFO, в ко­торой содержатся эти ребра так, чтобы на каждом проходе проверялись только они. На рис. 21.30 показан пример действия этого алгоритма.

Программа 21.9 эффективна для решения задачи поиска кратчайших путей в реальных сетях с единственным источником, однако быстродействие худшего случая все-таки ос­тается пропорциональной VE. Для плотных графов время выполнения не лучше, чем для алгоритма Флойда, который находит скорее все кратчайшие пути, а не только те, кото­рые исходят из единственного источника. Для разреженных графов реализация алгорит­ма Беллмана-Форда в программе 21.9 достигает коэффициента V, т.е. является более бы­строй, нежели алгоритм Флойда. Тем не менее, она близка к коэффициенту V, более медленному, чем худший случай времени выполнения, которого может показать алгоритм Дейкстры на сетях без ребер с отрицательными весами (см. таблицу 19.2).

Глава 21. Кратчайшие пути

РИСУНОК 21.30. АЛГОРИТМ

⇐ Предыдущая160161162163164165166167168169Следующая ⇒