![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 21. Кратчайшие пути. Для обозначения общего метода получения V проходов по ребрам с просмотром ребер в любом порядке мы будем использовать термин алгоритм Белпмана-Форда
Например, для графа, представленного списками смежных вершин, алгоритм Беллма-на-Форда поиска кратчайших путей из стартовой вершины 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. Алгоритмы на графах
Хотя это и не рассматривалось явно, то же самое доказательство показывает, что вектор 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 эффективна для решения задачи поиска кратчайших путей в реальных сетях с единственным источником, однако быстродействие худшего случая все-таки остается пропорциональной VE. Для плотных графов время выполнения не лучше, чем для алгоритма Флойда, который находит скорее все кратчайшие пути, а не только те, которые исходят из единственного источника. Для разреженных графов реализация алгоритма Беллмана-Форда в программе 21.9 достигает коэффициента V, т.е. является более быстрой, нежели алгоритм Флойда. Тем не менее, она близка к коэффициенту V, более медленному, чем худший случай времени выполнения, которого может показать алгоритм Дейкстры на сетях без ребер с отрицательными весами (см. таблицу 19.2). Глава 21. Кратчайшие пути
РИСУНОК 21.30. АЛГОРИТМ
|