Метод Форда-Беллмана решения задачи о кратчайшем пути в графе

Алгоритм Беллмана-Форда (Bellman-Ford algorithm)

Алгоритм Беллмана-Форда позволяет решить задачу о кратчайшем пути из одной вершины в общем случае, когда вес каждого из ребер может быть отрицательным. Для заданного взвешенного ориентированного графа G = (V, Е) с истоком s и весовой функцией w : Е —» R алгоритм Беллмана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует. Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес.

В этом алгоритме используется ослабление, в результате которого величина d[v], представляющая собой оценку веса кратчайшего пути из истока s к каждой из вершин v є V, уменьшается до тех пор, пока она не станет равна фактическому весу кратчайшего пути из s в v. Значение TRUE возвращается алгоритмом тогда и только тогда, когда граф не содержит циклов с отрицательным весом, достижимых из истока.

Формальное описание     [вверх]

Bellman_Ford(G, w, s) 1 Initialize_Single_Source(G, s) 2 for i «- l to |V[G]|-1 3 do for (для) каждого ребра (u, v) є E[G] 4 do RELAX(u,v,w) 5 for (для) каждого ребра (u, v) є E[G] 6 do if d[v] > d[u] + w(u, v) 7 then return FALSE 8 return TRUE

После инициализации в строке 1 всех значений d и prev, алгоритм осуществляет |V| — 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла for в строках 2-4 и состоит из однократного ослабления каждого ребра графа. После |V| — 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответству- ющее булево значение.

Оценка сложности     [вверх]

Алгоритм Беллмана-Форда завершает свою работу в течение времени O(V*E), поскольку инициализация в строке 1 занимает время O(V), на каждый из |V| — 1 проходов по ребрам в строках 2-4 требуется время в O(E), а на выполнение цикла for в строках 5-7 — время O(Е). .

Пример     [вверх ]

Визуализатор для алгоритма Беллмана-Форда.

Запустить визуализатор для алгоритма Беллмана-Форда


Выполнение алгоритма Беллмана-Форда:

На рисунке в вершинах графа показаны значения атрибутов d на каждом этапе работы алгоритма, а выделенные ребра указывают на значения предшественников: если ребро (u, v) выделено, то prev[v] = u. В рассматриваемом примере при каждом проходе ребра ослабляются в следующем порядке: (t, х), (t, у), (t, z), (x,t), (у,х), (у, z), (z,x), (z,s), (s,t), (s,y). В части а рисунка показана ситуация, сложившаяся непосредственно перед первым проходом по ребрам. В частях б-д проиллюстрирована ситуация после каждого очередного прохода по ребрам. Значения атрибутов d и prev, приведенные в части д, являются окончательными.


Если в графе, представленном выше, поменять вес дуги (1; 4) на -8, то мы получим отрицательный цикл из вершин 1-4-2 (дуги цикла отмечены красным цветом).

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

Метод Форда-Беллмана решения задачи о кратчайшем пути в графе

123456Следующая ⇒

Способы задания графов

Геометрический (графический)

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

Теоретико-множественный


Матричный

А) Матрица инцидентности

n-число вершин, m – число дуг или ребер

Для неорграфа:

Б) Матрица смежности

Неорграф:

Орграф:

Маршруты, цепи, циклы

Маршрутом в графе называется {x1,r1,x2,r2,…xn}

чередующиеся последовательность вершин и ребер/дуг.

Неорграф:

Цепьюρ=(r1, … rn) называется упорядоченная последовательность ребер в которой у каждого ребра ri одна из граничных вершин является граничной вершиной ri-1, а другие ri+1. Если вершины и ребра в цепи различны, то маршрут называют простой цепью. Замкнутая цепь называется циклом, а замкнутая простая цепь называется простым циклом.

Орграф:

Путем в графе называется упорядоченная последовательность дуг μ = (U1, …, Un), в которой конец предыдущей дуги совпадает с началом последующей. Путь у которого начальные и конечные вершины совпадают – контур. Длина цепи– число ребер в цепи. Граф называется связным, если любая пара его вершин соединены цепью. Минимальная длина цепи, соединяющая вершины xi и xjназывается расстоянием. Максимальное расстояние между вершинами графа называется диаметром графа. . Цепь (неорграф) называют составной, если в ней повторяется хотя бы одно ребро; сложной, если повторяется хотя бы одна вершина. Простой цикл называется гамильтоновым, если он проходит через каждую вершину графа ровно 1 раз. В орграфе путь, проходящий через все вершины ровно 1 раз, называется гамильтоновым, если у него начальная и конечная вершина совпадают, то гамильтонов контур.

 

 

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

Пусть l(xi) – пометка вершины xi.

Шаг 1. Присвоение начальных значений. Положить l*(s)=0 и считать эту пометку постоянной. Положить l(xi)=∞ (бесконечность) для всех xi¹s и считать эти пометки временными. Положить р=s.

Шаг 2. Обновление пометок. Для всех вершин xiÎГ(р), имеющих временные пометки, изменить пометки в соответствии с выражением:

l(xi) = min{l(xi), l(p) + c(p, xi)}. (2.3)

Шаг 3.

Метод Форда-Беллмана решения задачи о кратчайшем пути в графе

Превращение пометки в постоянную. Среди всех вершин с временными пометками найти такую, для которой l*(xi) = min{l(xi)}.

Шаг 4. Считать пометку вершины xi* постоянной и положить p = xi*.

Шаг 5. Если р=t, то l*(р) является длиной кратчайшего пути. Конец.
Если р¹t, перейти к шагу 2.

Как только длина кратчайшего пути от s до t будет найдена [она будет постоянной пометкой вершины l*(t)], сами пути можно получить с помощью рекурсивной процедуры. Так, для вершины xk, непосредственно предшествующей вершине t в кратчайшем пути от s к t, будет соблюдаться отношение: l*(xk) + c(xk, t) = l*(t).

Таким образом, для любой вершины xi можно найти предшествующую вершину xk, принадлежащую пути m(s, t), для которой справедливо:

l*(xk) + c(xk, xi) = l*(xi). (2.4)

Если существуют несколько кратчайших путей от s к t, то данное соотношение будет выполняться для нескольких вершин. В этом случае выбор пути может быть произвольным.

 

Метод Форда-Беллмана решения задачи о крат
чайшем пути в графе.

Алгоритм Ф.Б. позволяет находить кратчайшие пути от источника S до любой вершины, при этом веса дуг могут быть как “+”, так и “-“.

Исходные данные: граф C помечен дугами, а результат помечен вершинами.

1) Присвоение начального значения меток

Установить номер итерации k=0, присвоить начальное значение меток следующим образом:

2) Обновление пометки вершин

Для каждой вершины Xj =Г(S) установить пометку следующим образом:

Где Tj = Г-1множество вершины, которые входят в Xj и связан с вершиной X

3) Проверка условий окончания

Если k <= n-1 и Пк+1 (Xj) != Пк (Xj) хотя бы для 1 вершины, то переход к шагу 4 если

Пк+1 (Xj) = Пк (Xj), то конец алгоритма.

4) Подготовка к следующей итерации

Определить множество S, как множество таких X, что

Пометки П (Xi) у всех вершин графа характеризуют расстояние от источника Х1 до данной вершины.

 

 


123456Следующая ⇒


Дата добавления: 2016-07-29; просмотров: 1256 | Нарушение авторских прав


Похожая информация:


Поиск на сайте:


Похожие главы из других работ:

Графы

4.1 Алгоритм Дейкстры (алгоритм расстановки меток)

Неформальное объяснение: Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки…

Кольцо целых чисел Гаусса

1.3 НОД. АЛГОРИТМ ЕВКЛИДА.

Мы пользуемся обычным для колец определением наибольшего общего делителя. НОДом двух гауссовых чисел называется такой их общий делитель, который делится на любой другой их общий делитель. Как и во множестве целых чисел…

Метод гілок та меж для рішення задач цілочисельного програмування

Алгоритм рішення

Дана матриця відстаней, представлена в таблиці 1. Необхідно за допомогою алгоритму Літтла вирішити завдання комівояжера. Табл…

Метод многомерной нелинейной оптимизации – метод наискорейшего спуска

2. Алгоритм программы

Размещено на http://www.allbest…

Методы отсечения

6. Алгоритм Данцига

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

Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

2.2 Алгоритм Дейкстры

Для нахождения кратчайшего пути между двумя конкретными вершинами s и t широко применяется алгоритм Дейкстры. Далее рассмотрим шаги данного алгоритма. Шаг 1. перед началом выполнения алгоритма дуги не окрашены…

Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

2.4 Алгоритм Флойда

Алгоритм Флойда — это алгоритм поиска кратчайших путей между всеми вершинами графа. Пусть дан взвешенный орграф с n вершинами и матрицей весов W. Каждый элемент матрицы весов w равен весу дуги <x, x> (если такой дуги нет, то w), а w=0 . Предположим…

Поиск оптимального пути в ненагруженном орграфе

Алгоритм поиска минимального пути из в в ориентированном орграфе (алгоритм фронта волны)

1) Помечаем вершину индексом 0, затем помечаем вершины О образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1. 2) Если или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается. В противном случае продолжаем: 3) Если…

Полином Жегалкина

Алгоритм

булевой функция полином жигалкин В данной программе был реализован метод неопределенных коэффициентов для построения полинома Жегалкина. 1. Получить таблицу истинности для определенного количества переменных; 2…

Решение задачи коммивояжера методом ветвей и границ

4. Алгоритм решения

Дана матрица расстояний, представленная в таблице 1. Необходимо с помощью алгоритма Литтла решить задачу коммивояжера. Табл…

Решение некоторых уравнений и неравенств с параметром

2. Алгоритм решения

· Алгоритм решения уравнения с параметром аналитически. 1. Определяют ограничения, налагаемые на значения неизвестного x и параметра a, вытекающие из того, что функции и арифметические операции в F (x, a) имеют смысл. 2…

Решение уравнений, неравенств, систем с параметром

2. Алгоритм решения.

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

Системный анализ групп преобразований состояний кубика Рубика

3.4.1 Алгоритм Тистлетуэйта

Тистлетуэйт использовал ряд подгрупп длины 4 · G0 = (L, R, F, B, U, D) Эта группа совпадает с группой кубика Рубика. Её порядок равен · G1 = (L2, R2, F, B, U, D) Эта подгруппа включает в себя все состояния…

Теорема Ляпунова

1. Алгоритм

Ляпунов предложил простой и очень эффективный метод построения периодических решений для достаточно малых значений постоянной с решения системы (1.8)…

Теория остатков

1.2 Алгоритм Евклида

Определение. Число d ??Z , делящее одновременно числа а , b , c , … , k ??Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем.

Алгоритм Беллмана — Форда.

Обозначение: d = ( a , b , c , …, k ) . Теорема. Если ( a , b ) = d…

Метод Форда — Беллмана

Предыдущая12345678Следующая

 

Данный метод обеспечивает нахождение кратчайших путей m[s, xi] между источником s и всеми другими вершинами xi Î X \ s для ориентированного графа G = (X, U), в котором отсутствуют контуры суммарной отрицательной длины. Веса дуг l(xi, xj) могут иметь любые значения. Метод является итерационным и основан на изменении пометок вершин графа, причем значения (xi) в конце k-й итерации равны длинам таких кратчайших путей m[s, xj], которые содержат не более k + 1 дуг.

Ниже приводится формальная схема алгоритма, реализующая метод Форда — Беллмана.

 

Алгоритм 1.1 (метод Форда — Беллмана)

 

Данные: орграф G = (X, U), имеющий n вершин, с выделенным иcточником s Î X; веса дуг l(xi, xj) для всех (xi, xj) Î U.

Результаты: длины l*(xi) кратчайших путей m[s, xi] для всех xi Î X \ s.

Шаг 1 (присвоение начальных значений)

Установить номер итерации k = 0. Определить множество вершин
S = Г(s). Присвоить начальные значения пометкам:

Шаг 2 (обновление пометок вершин)

Для каждой вершины xj ÎГ(S) изменить пометку:

,

где .

Пометки вершин xj Ï Г(S) не изменять и присвоить

.

Шаг 3 (проверка условий окончания)

а) Если k £ n — 1 и для всех xiÎ X, то получен оптимальный результат , i = . Конец алгоритма.

б) Если k < n — 1 и хотя бы для одной вершины
xi Î X, то выполнить переход к шагу 4.

в) Если k = n — 1 и для некоторой xi Î X, то в графе G существует цикл суммарной отрицательной длины и задача не имеет решения. Конец алгоритма.

Шаг 4 (подготовка к следующей итерации)

Определить множество S следующим образом:

.

Изменить номер итерации k = k + 1 и выполнить переход к шагу 2.

 

Следует отметить, что на шаге 2 множество S содержит все вершины xi графа, для которых кратчайшие пути m[s, xi] состоят из k дуг. Множество Tj определяет вершины из множества S, связанные дугами с xj. Если
xj Ï Г(S), то кратчайший путь из s в xj не может состоять из k + 1 дуг и поэтому пометки таких вершин l(xj) изменять не требуется. На шаге 4 новое множество S содержит все вершины, кратчайшие пути до которых содержат k + 1 дуг.

Представленный алгоритм обеспечивает получение оптимального решения. Доказательство приводится в работах [6, 10] и базируется на принципах динамического программирования и том факте, что если не существует никакого оптимального пути из k дуг, то не может также существовать никакого оптимального пути, содержащего k + 1 дуг.

Вычислительная сложность метода Форда — Беллмана имеет оценку О(n3), т. е. в случае полного связного графа с n вершинами требуется порядка n3 операций сложения и сравнения. Алгоритм 1.1 можно использовать и в случае неотрицательных весов дуг, но более предпочтительным является применение алгоритма Дейкстры, так как его оценка трудоемкости составляет О(n2) операций.

Пример 1.1. Применение метода Форда — Беллмана для графа G = (X, U), приведенного на рис. 1.2 и заданного матрицей D (см. упражнение 1.12), показано в табл. 1.2. Предполагается, что источником s является вершина x1. Окончательные значения пометок l*(xi) равны 0, 1, 4, 3, -1 для вершин xi, , соответственно. Кратчайшие пути m[s, xi], где s = x1 и , получены с использованием соотношения (1.2). Результаты решения задачи, включая дерево кратчайших путей, представлены на рис. 1.3.

 

Рис. 1.2. Представление графа для примера 1.1

 

 

У П Р А Ж Н Е Н
И Я

 

1.15.

Определить особенности графовых моделей, для которых может применяться метод Форда — Беллмана.

1.16. Какое наибольшее число итераций может потребоваться при работе алгоритма 1.1? Изменится ли это значение, если веса всех дуг графа будут неотрицательными?

1.17. Решить задачу построения кратчайших путей m[x2, x5] и m[x5, x2] для графа, показанного на рис. 1.2.

1.18. Разработать подпрограммы формирования множеств S, Г(S) и Tj для xjÎ Г(S).

1.19. Разработать подпрограммы вычисления меток вершин и проверки условий окончания итерационного процесса для метода Форда -Беллмана.

1.20. Модифицировать алгоритм 1.1 таким образом, чтобы для построения кратчайших путей использовать пометки вида [l*(xj), mj], описанные в предыдущем разделе.

Таблица 1.2

Результаты работы алгоритма Форда — Беллмана (пример 1.1)

Итерация Множество S Множество Г(S) Вершина Множество Ti Пометка l(xi)
k = 0 {x2, x5}   s = x1x2x3x4x5     ¥ ¥
k = 1 {x2, x5} {x2, x3, x4, x5} x1x2x3x4x5   {x5} {x2} {x2 ,x5} {x2} min(1, 3+8) = 1 min(¥, 1+3) = 4 min(¥, 1+3, 3+4) = 4 min(3, 1+8) = 3
k = 2 {x3, x4} {x3, x4, x5} x1x2x3x4x5     {x4} {x3} {x3} min(4, 4+2) = 4 min(4, 4+1) = 4 min(3, 4-5) = -1
k = 3 {x5} {x2, x4} x1x2x3x4x5   {x5}   {x5} min(1, -1+8) = 1 min(4, -1+4) = 3 -1
k = 4 {x4} {x3} x1x2x3x4x5     {x4} min(4, 3+2) = 4 -1

 

1.21. Решить задачу из примера 1.1 по алгоритму, полученному при выполнении упражнения 1.20.

1.22.

Алгоритм Дейкстры. Алгоритм Форда-Беллмана

Составить программы поиска кратчайших путей по методу Форда — Беллмана для двух способов построения путей (см. раздел 1.2).

 

Рис. 1.3. Результаты поиска путей (пример 1.1)

1.23. Получить (машинное) решение задачи вычисления длин кратчайших путей m[x1, xj], , для графа, показанного на рис. 1.4.

Ответ: вектор значений l*(xi), , имеет следующий вид:

(0, -3, -11, -5, 2, -7, -1, 13, 16).

Рис. 1.4. Представление графа для упражнения 1.23

Предыдущая12345678Следующая

Date: 2015-10-21; view: 1454; Нарушение авторских прав

Понравилась страница? Лайкни для друзей:

Алгоритм Форда – Беллмана нахождения минимального пути

Задан ориентированный взвешенный граф, содержащий, возможно, дуги отрицательного веса. Необходимо найти веса кратчайших путей от вершины v до всех остальных вершин.

Входные данные:

В первой строке записаны целые числа N и M – количество вершин и количество дуг соответственно (, ). Дальше идет M строк с тройками целых чисел X, Y, W, обозначающими, что дуга из X в Y имеет вес W (, ). В последней строке записано число v – номер стартовой вершины ().

Выходные данные:
Если в графе есть циклы отрицательного веса и потому не все кратчайшие пути определены, вывести «INCORRECT INPUT». В противном случае вывести N строк – веса кратчайших путей от вершины v до всех остальных вершин, включая её саму, в порядке возрастания номера второй вершины. Если до вершины дойти нельзя, то в соответствующей строке необходимо вывести «NO».

Реализация решения

[cc lang=»delphi»]{$APPTYPE CONSOLE}

const
inf = $7FFFFFFF;

type
TEdge = record
from: integer;
to1: integer;
l: integer;
end;

var
n, m, i, j, v: integer;
t: array [0 .. 1000] of longint;
edges: array [0 .. 10000] of TEdge;

begin
read(n);
readln(m);

for i := 0 to m — 1 do
begin
read(edges[i].from, edges[i].to1);
readln(edges[i].l);

dec(edges[i].from);
dec(edges[i].to1);
end;

readln(v);
dec(v);

for i := 0 to n — 1 do
t[i] := inf;

t[v] := 0;

for i := 1 to n do
for j := 0 to m — 1 do
if (t[edges[j].from] < inf) and (t[edges[j].from] + edges[j].l < t[edges[j].to1]) then if i = n then begin writeln('INCORRECT INPUT'); exit; end else t[edges[j].to1] := t[edges[j].from] + edges[j].l; for i := 1 to n - 1 do begin if (t[i] = inf) then writeln('NO') else writeln(t[i]); end; end.[/cc]

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *