Предполагается, что ориентированный граф не содержит контуров отрицательной длины
жүктеу/скачать 55,97 Kb.
|
Алгоритм ФордаБеллмана пр
- Бұл бет үшін навигация:
- Рис. 3.10
- Таблица 3.1
|
Алгоритм Форда – Беллмана нахождения минимального пути Предполагается, что ориентированный граф не содержит контуров отрицательной длины.Алгоритм 3.1 (Алгоритм Форда – Беллмана). Основными вычисляемыми величинами этого алгоритма являются величины j(k), где i = 1, 2, … , n (n – число вершин графа); k = 1, 2, … , n – 1. Для фиксированных i и k величина j(k) равна длине минимального пути, ведущего из заданной начальной вершины х1 в вершину хi и содержащего не более k дуг. Шаг 1. Установка начальных условий. Ввести число вершин графа n и матрицу весов C = (cij). Шаг 2. Положить k = 0. Положить i(0) = ¥ для всех вершин, кроме х1; положить 1(0) = 0. Шаг 3. В цикле по k, k = 1,..., n – 1, каждой вершине xi на k-ом шаге приписать индекс i(k) по следующему правилу: i(k) = {j(k – 1) + cji} (3.1) для всех вершин, кроме х1, положить 1(k) = 0. В результате работы алгоритма формируется таблица индексов i(k), i = 1, 2, … , n, k = 0, 1, 2, … , n – 1. При этом i(k) определяет длину минимального пути из первой вершины в i-ую, содержащего не более k дуг. Шаг 5. Восстановление минимального пути. Для любой вершины xs предшествующая ей вершина xr определяется из соотношения: r(n – 2) + crs = s(n – 1), xrÎ G-1(xs), (3.2) где G-1(xs) - прообраз вершины xs. Для найденной вершины xr предшествующая ей вершина xq определяется из соотношения: q(n – 3) + cqr = r(n – 2), xqÎ G-1(xr), где G-1(xr) - прообраз вершины xr, и т. д. Последовательно применяя это соотношение, начиная от последней вершины xi , найдем минимальный путь. Пример 3.15. С помощью алгоритма 3.1 найдем минимальный путь из вершины х1 в вершину х3 в графе, изображенном на рис. 3.10. Рис. 3.10Рассмотрим подробно работу алгоритма Форда – Беллмана для этого примера. Значения индексов i(k) будем заносить в таблицу индексов (табл. 3.1). Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа имеет вид: C = . Шаг 2. Положим k = 0, 1(0) = 0, 2(0) = 3(0) = 4(0) = 5(0) = ¥. Эти значения занесем в первый столбец табл. 3.1. Шаг 3. k = 1. 1(1) = 0. Равенство (7.1) для k = 1 имеет вид: i(1) = {j(0) + cji}. 2(1) = min{1(0) + c12; 2(0) + c22; 3(0) + c32; 4(0) + c42; 5(0) + c52;} = min{0 + 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = 1. 3(1) = min{1(0) + c13; 2(0) + c23; 3(0) + c33; 4(0) + c43; 5(0) + c53;} = min{0 + ¥ ; ¥ + 8; ¥ + ¥; ¥ + 2; ¥ + ¥} = ¥ . 4(1) = min{1(0) + c14; 2(0) + c24; 3(0) + c34; 4(0) + c44; 5(0) + c54;} = min{0 + ¥ ; ¥ + 7; ¥ + 1; ¥ + ¥; ¥ + 4} = ¥ . 5(1) = min{1(0) + c15; 2(0) + c25; 3(0) + c35; 4(0) + c45; 5(0) + c55;} = min{0 + 3; ¥ + 1; ¥ – 5; ¥ + ¥; ¥ + ¥} = 3. Полученные значения i(1) занесем во второй столбец табл. 3.1. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин i(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги. k = 2. 1(2) = 0. Равенство (3.1) для k = 2 имеет вид: i(2) = {j(1) + cji}. 2(2) = min{0 + 1; 1 + ¥; ¥ + ¥; ¥ + ¥; 3 + ¥} = 1. 3(2) = min{0 + ¥ ; 1 + 8; ¥ + ¥; ¥ + 2; 3 + ¥} = 9 . 4(2) = min{0 + ¥ ; 1 + 7; ¥ + 1; ¥ + ¥; 3 + 4} = 7 . 5(2) = min{0 + 3; 1 + 1; ¥ – 5; ¥ + ¥; 3 + ¥} = 2. Полученные значения i(2) занесем в третий столбец табл. 3.1. Величины i(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг. k = 3. 1(3) = 0. Равенство (3.1) для k = 3 имеет вид: i(3) = {j(2) + cji}. 2(3) = min{0 + 1; 1 + ¥; 9 + ¥; 7 + ¥; 2 + ¥} = 1. 3(3) = min{0 + ¥ ; 1 + 8; 9 + ¥; 7 + 2; 2 + ¥} = 9 . 4(3) = min{0 + ¥ ; 1 + 7; 9 + 1; 7 + ¥; 2 + 4} = 6 . 5(3) = min{0 + 3; 1 + 1; 9 – 5; 7 + ¥; 2 + ¥} = 2. Полученные значения i(3) занесем в четвертый столбец табл. 3.1. Величины i(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг. k = 4. 1(4) = 0. Равенство (3.1) для k = 4 имеет вид: i(4) = {j(3) + cji}. 2(4) = min{0 + 1; 1 + ¥; 9 + ¥; 6 + ¥; 2 + ¥} = 1. 3(4) = min{0 + ¥ ; 1 + 8; 9 + ¥; 6 + 2; 2 + ¥} = 8 . 4(4) = min{0 + ¥ ; 1 + 7; 9 + 1; 6 + ¥; 2 + 4} = 6 . 5(4) = min{0 + 3; 1 + 1; 9 – 5; 6 + ¥; 2 + ¥} = 2. Полученные значения i(4) занесем в пятый столбец табл. 3.1. Величины i(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг. Таблица 3.1
Шаг 5. Восстановление минимального пути. Для последней вершины x3 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =3: r(3) + cr3 = 3(4), xrÎ G-1(x3), (3.3) где G-1(x3) - прообраз вершины x3. G-1(x3) = {x2, x4}. Подставим в (3.3) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется: 2(3) + c23 = 1 + 8 ¹ 3(4) = 8, 4(3) + c43 = 6 + 2 = 3(4) = 8. Таким образом, вершиной, предшествующей вершине x3, является вершина x4. Для вершины x4 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4: r(2) + cr4 = 4(3), xrÎ G-1(x4), (3.4) где G-1(x4) - прообраз вершины x4. G-1(x4) = {x2, x3, x5}. Подставим в (3.4) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется: 2(2) + c24 = 1 + 7 ¹ 4(3) = 6, 3(2) + c34 = 1 + 1 ¹ 4(3) = 6, 5(2) + c54 = 2 + 4 = 4(3) = 6, Таким образом, вершиной, предшествующей вершине x4, является вершина x5. Для вершины x5 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =5: r(1) + cr5 = 5(2), xr G-1(x5), (3.5) где G-1(x5) - прообраз вершины x5. G-1(x5) = {x1, x2}. Подставим в (3.5) последовательно r = 1 и r = 2, чтобы определить, для какого r это равенство выполняется: 1(1) + c15 = 0 + 3 ¹ 5(2) = 2, 2(1) + c25 = 1 + 1 = 5(2) = 2, Таким образом, вершиной, предшествующей вершине x5, является вершина x2. Для вершины x2 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2: r(0) + cr2 = 2(1), xr G-1(x2), (3.6) где G-1(x2) - прообраз вершины x2. G-1(x2) = {x1}. Подставим в (3.6) r = 1, чтобы определить, выполняется ли это равенство: 1(0) + c12 = 0 + 1 = 2(1) = 1. Таким образом, вершиной, предшествующей вершине x2, является вершина x1. Итак, найден минимальный путь – x1, x2, x5, x4, x3, его длина равна 8. 3.9. Алгоритм нахождения максимального пути При решении некоторых практических задач возникает необходимость поиска максимального пути (пути с наибольшей суммой длин дуг). Такая задача сводится к задаче нахождения минимального пути заменой знаков при длинах дуг (в матрице весов C) на противоположные. При этом необходимым является требование отсутствия в ориентированном графе контуров положительной длины. Пример 3.16. С помощью модифицированного алгоритма 3.1 найдем максимальный путь из вершины х1 в вершину х3 в графе, изображенном на рис. 3.11. Рис. 3.11 Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа после замены знаков при длинах дуг на противоположные имеет вид: C = . Шаг 2. Положим k = 0, 1(0) = 0, 2(0) = 3(0) = 4(0) = 5(0) = . Эти значения занесем в первый столбец табл. 3.2. Шаг 3. k = 1. 1(1) = 0. Равенство (3.1) для k = 1 имеет вид: i(1) = {j(0) + cji}. 2(1) = min{1(0) + c12; 2(0) + c22; 3(0) + c32; 4(0) + c42; 5(0) + c52;} = min{0 – 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = –1. 3(1) = min{1(0) + c13; 2(0) + c23; 3(0) + c33; 4(0) + c43; 5(0) + c53;} = min{0 + ¥ ; ¥ – 8; ¥ + ¥; ¥ – 2; ¥ + ¥} = ¥ . 4(1) = min{1(0) + c14; 2(0) + c24; 3(0) + c34; 4(0) + c44; 5(0) + c54;} = min{0 + ¥ ; ¥ – 7; ¥ + ¥; ¥ + ¥; ¥ – 4} = ¥ . 5(1) = min{1(0) + c15; 2(0) + c25; 3(0) + c35; 4(0) + c45; 5(0) + c55;} = min{0 – 3; ¥ – 1; ¥ + 5; ¥ + ¥; ¥ + ¥} = –3. Полученные значения i(1) занесем во второй столбец табл. 3.2. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин i(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги. k = 2. 1(2) = 0. Равенство (3.1) для k = 2 имеет вид: i(2) = {j(1) + cji}. 2(2) = min{0 – 1; –1 + ¥; ¥ + ¥; ¥ + ¥; –3 + ¥} = –1. 3(2) = min{0 + ¥ ; –1 – 8; ¥ + ¥; ¥ – 2; –3 + ¥} = –9 . 4(2) = min{0 + ¥ ; –1 – 7; ¥ + ¥; ¥ + ¥; –3 – 4} = –8 . 5(2) = min{0 – 3; –1 – 1; ¥ + 5; ¥ + ¥; –3 + ¥} = –3. Полученные значения i(2) занесем в третий столбец табл. 3.2. Величины i(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг. k = 3. 1(3) = 0. Равенство (3.1) для k = 3 имеет вид: i(3) = {j(2) + cji}. 2(3) = min{0 – 1; – 1 + ¥; – 9 + ¥; –8 + ¥; – 3 + ¥} = – 1. 3(3) = min{0 + ¥ ; – 1 – 8; – 9 + ¥; –8 – 2; – 3 + ¥} = – 10 . 4(3) = min{0 + ¥ ; – 1 – 7; – 9 + ¥; –8 + ¥; – 3 – 4} = – 8 . 5(3) = min{0 – 3; – 1 – 1; – 9 + 5; –8 + ¥; – 3 + ¥} = – 4. Полученные значения i(3) занесем в четвертый столбец табл. 3.2. Величины i(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг. k = 4. 1(4) = 0. Равенство (3.1) для k = 4 имеет вид: i(4) = {j(3) + cji}. 2(4) = min{0 – 1; – 1 + ¥ ; – 10 + ¥; – 8 + ¥; – 4 + ¥} = – 1. 3(4) = min{0 + ¥ ; – 1 – 8; – 10 + ¥; – 8 – 2; – 4 + ¥} = – 10 . 4(4) = min{0 + ¥ ; – 1 – 7; – 10 + ¥; – 8 + ¥; – 4 – 4} = – 8 . 5(4) = min{0 – 3; – 1 – 1; – 10 + 5; – 8 + ¥; – 4 + ¥} = – 5. Полученные значения i(4) занесем в пятый столбец табл. 3.2. Величины i(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг. Таблица 3.2
Заменив в табл. 3.2 отрицательные числа положительными, получим таблицу индексов максимальных путей (табл. 3.3). При этом i(k) определяет длину максимального пути из первой вершины в i-ую, содержащего не более k дуг. Таблица 3.3
Шаг 5. Восстановление максимального пути производится по тому же правилу, что и для минимального пути. Длина максимального пути равна 10. Этот путь состоит из трех дуг, т. к. i(3) = i(4) = 10. Поэтому в соотношении (3.2) будет выполнено, начиная с n – 1. Учитывая это замечание, для последней вершины x3 предшествующую ей вершину xr определим из соотношения (3.2) полученного при s =3: r(2) + cr3 = 3(3), (3.7) xrÎ G-1(x3), где G-1(x3) - прообраз вершины x3. G-1(x3) = {x2, x4}. Подставим в (3.7) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется: 2(2) + c23 = 1 + 8 ¹ 3(4) = 10, 4(2) + c43 = 8 + 2 = 3(4) = 10. Таким образом, вершиной, предшествующей вершине x3, является вершина x4. Для вершины x4 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4: r(1) + cr4 = 4(2), xrÎ G-1(x4), (3.8) где G-1(x4) - прообраз вершины x4. G-1(x4) = {x2, x5}. Подставим в (3.8) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется: 2(1) + c24 = 1 + 7 = 4(3) = 8, 5(1) + c54 = 3 + 4 ¹ 4(3) = 8, Таким образом, вершиной, предшествующей вершине x4, является вершина x2. Для вершины x2 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2: r(0) + cr2 = 2(1), xr G-1(x2), (3.9) где G-1(x2) - прообраз вершины x2. G-1(x2) = {x1}. Подставим в (3.9) r = 1, чтобы определить, выполняется ли это равенство: 1(1) + c12 = 0 + 1 = 2(1) = 1. Таким образом, вершиной, предшествующей вершине x2, является вершина x1. Итак, найден максимальный путь – x1, x2, x4, x3, его длина равна 10. жүктеу/скачать 55,97 Kb. Достарыңызбен бөлісу:
|