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

Читайте также:

Шаг 1. Составим матрицу длин дуг C(G)=[Cij]n

	v₁	v₂	v₃	v₄	v₅	v₆
v₁	∞	∞
v₂	∞	∞	∞	∞	∞
v₃	∞		∞	∞	∞	∞
v₄	∞		∞	∞	∞	∞
v₅	∞	∞			∞	∞
v₆	∞	∞	∞	∞	∞	∞

Строки и столбцы соответствует вершинам v₁,...,v₆.

По диагонали ставим ∞. Заполняем строку v₁: если существует дуга из v₁ в вершину, то в соответствующем этой вершине столбце ставим число, равное длине дуги, в противном случае ставим ∞.

	l_i⁽⁰⁾	l_i⁽¹⁾	l_i⁽²⁾	l_i⁽³⁾	l_i⁽⁴⁾	l_i⁽⁵⁾
v₁	0	0	0	0	0	0
v₂	∞	∞	∞	∞	∞
v₃	∞		∞	∞	∞	∞
v₄	∞		∞	∞	∞	∞
v₅	∞				∞	∞
v₆	∞		∞	∞	∞	∞

Шаг 2. Рядом с матрицей длин дуг составляем таблицу величин l_i⁽^k⁾, i = 1..6, k = 1..5.

Матрица длин дуг таблица величина дуг л_i⁽^k⁾

v₁ v₂ v₃ v₄ v₅ v₆

v₁ ∞ ∞

v₂ ∞ ∞ ∞ ∞ ∞

v₃ ∞ ∞ ∞ ∞ ∞

v₄ ∞ ∞ ∞ ∞ ∞

v₅ ∞ ∞ ∞ ∞

v₆ ∞ ∞ ∞ ∞ ∞ ∞

Заполняем первый столбец l_i⁽⁰⁾ таблицы: его элементами будут 0, ∞, ∞, ∞, ∞, ∞, т.к. для v₁l₁⁽⁰⁾=0 (длина минимального пути содержащего ноль дуг из v₁ в v₁ ровно 0), для v₂l₂⁽⁰⁾= ∞ (длина минимального пути, содержащего ноль дуг, из v₁ в v₂ ровно (такого пути нет)), для v₃l₃⁽⁰⁾= ∞, для v₄ l₄⁽⁰⁾= ∞, для v₅ l₅⁽⁰⁾= ∞, для v₆ l₆⁽⁰⁾= ∞.

Заполняем первую строку таблицы: ее элементами будут 0, 0, 0, 0, 0, 0, т.к. длина минимального пути, содержащего ноль дуг из v₁ в v₁ равна нулю l₁⁽⁰⁾=0, длина минимального пути, содержащего одну дугу из v₁ в v₁ равна нулю, l₁⁽¹⁾=0, l₁⁽²⁾=0, l₁⁽³⁾=0, l₁⁽⁴⁾=0, l₁⁽⁵⁾=0.

Заполняем второй столбец l_i⁽¹⁾ таблицы: берем второй столбец v₂ матрицы длин дуг и первый столбец таблицы l_i⁽⁰⁾ и сложим их поэлементно

v₂ = ∞ l_i⁽⁰⁾ = v₂+l_i⁽⁰⁾= ∞

∞ ∞ ∞

∞ ∞

∞ ∞

∞ ∞ ∞

∞ ∞ ∞

Получили столбец v₂+l_i⁽⁰⁾, выберем минимальный элемент этого столбца (у нас получилась ∞, т.к. все элементы равны ∞), запишем это число ∞ в строку v₂ таблицы.

Далее

v₃ = 5 l_i⁽⁰⁾ = v₃+l_i⁽⁰⁾= 5

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

1 ∞ ∞

∞ ∞ ∞

Минимальный элемент v₃+l_i⁽⁰⁾ равен 5, запишем это число (5) в строку v₃ таблицы.

v₄ = 5 l_i⁽⁰⁾ = v₄+l_i⁽⁰⁾= 5

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

2 ∞ ∞

∞ ∞ ∞

Минимальный элемент v₄+l_i⁽⁰⁾ равен 5, запишем это число (5) в строку v₄ таблицы.

v₅ = 2 l_i⁽⁰⁾ = v₅+l_i⁽⁰⁾= 2

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

min = 2

v₆ = 12 l_i⁽⁰⁾ = v₆+l_i⁽⁰⁾= 12

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

min = 12

Заполняем третий столбец л_i⁽²⁾ таблицы: берем уже заполнений столбец л_i⁽¹⁾ и складываем его опять со столбцами матрицы дуг v₂, v₃, v₄, v₅, v₆.

l_i⁽¹⁾ = 0 v₂ = ∞ l_i⁽¹⁾+v₂= ∞

∞ ∞ ∞

5 2 ∞

5 2 ∞

2 ∞ ∞

12 ∞ ∞

min = 7

l_i⁽¹⁾ = 0 v₃ = 5 l_i⁽¹⁾+v₃= 5

∞ ∞ ∞

5 ∞ ∞

5 ∞ ∞

2 1 ∞

12 ∞ ∞

min = 3

l_i⁽¹⁾ = 0 v₄ = 5 l_i⁽¹⁾+v₄= 5

∞ ∞ ∞

5 ∞ ∞

5 ∞ ∞

2 2 ∞

12 ∞ ∞

min = 4

l_i⁽¹⁾ = 0 v₅ = 2 l_i⁽¹⁾+v₅= 2

∞ ∞ ∞

5 ∞ ∞

5 ∞ ∞

2 ∞ ∞

12 ∞ ∞

min = 2

l_i⁽¹⁾ = 0 v₆ = 12 l_i⁽¹⁾+v₆= 12

∞ 2 ∞

5 ∞ ∞

5 ∞ ∞

2 ∞ ∞

12 ∞ ∞

min = 12

Заполняем четвертый столбец l_i⁽³⁾ таблицы: столбец l_i⁽²⁾ складываем поочередно со столбцами матрицы дуг v₂, v₃, v₄, v₅, v₆.

Пятый столбец l_i⁽⁴⁾: столбец l_i⁽³⁾ складываем поочередно со столбцами v₂, v₃, v₄, v₅, v₆..

Шестой столбец l_i⁽⁵⁾: столбец l_i⁽⁴⁾ складываем поочередно со столбцами v₂, v₃, v₄, v₅, v₆.

Шаг 3. В полученной таблице в строке v₆ последнее число равно 7 - это и есть длина минимального пути из v₁ в v₆..

l(v₁,v₆) = 7.

Теперь восстановим путь. Число 7 появилась первый раз в столбце л_i⁽⁴⁾, выделим его в кружок. Число 7 появилась в результате

l_i⁽³⁾ = 0 v₆ = 12 l_i⁽¹⁾+v₆= 12

5 2 7

3 ∞ ∞

4 ∞ ∞

2 ∞ ∞

9 ∞ ∞

min = 12

В таблице число 5 обведите в кружок, 2 - в квадрат и поставьте стрелку от 5 → 7. Число 5 появилась в результате

l_i⁽²⁾ = 0 v₂ = ∞ l_i⁽³⁾+v₂= ∞

7 ∞ ∞

3 2 5

4 2 6

2 ∞ ∞

12 ∞ ∞

В таблице число 3 обведите в кружок, 2 - в квадрат и поставьте стрелку от 3 → 5. Число 3 появилось в результате

l_i⁽¹⁾ = 0 v₃ = 5 l_i⁽³⁾+v₃= 5

∞ ∞ ∞

5 ∞ ∞

5 ∞ ∞

2 1 3

12 ∞ ∞

1 2 и 2 → 3

Число 2 появилось в результате

l_i⁽⁰⁾ = 0 v₅ = 2 l_i⁽³⁾+v₅= 2

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

∞ ∞ ∞

0 2 и 0 → 2

У нас получилось:

Число ноль стоит в строке v₁, 2 в строке v₅, 3-в v₃, 5 - в v₂, 7 - в v₆.

Восстанавливаем путь: v₁ → v₅ → v₃ → v₂ → v₆.

Итак, получили минимальный путь из v₁ в v₆ длины 7, проходящий через вершины v₁, v₅, v₃, v₂, v₆.

Определение: граф со взвешенными вершинами

Иногда веса (числа v_i) приписываются вершинам х_i графа, и тогда получается граф со взвешенными вершинами.

Определение: граф взвешенный

Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным. Чаще взвешенным называют граф со взвешенными вершинами.

Определение: вес (длина, стоимость) пути

При рассмотрении пути м представленного последовательностью дуг (a₁, a₂,..., a_q), за его вес (или длину, или стоимость) принимается число l(м), равное сумме весов всех дуг, входящих в м. Каждая дуга рассматривается столько раз, сколько она встречается в данном пути.

Основные определения и понятия теории графов:

петля,

контур,

цикл,

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

<== предыдущая страница	\|	следующая страница ==>
Граф со взвешенными дугами	\|	Неотрицательная матрица весов

mybiblioteka.su - 2015-2024 год. (0.013 сек.)

v₂ =	∞	l_i⁽⁰⁾ =	v₂+l_i⁽⁰⁾=	∞
∞	∞	∞
	∞	∞
	∞	∞
∞	∞	∞
∞	∞	∞

v₃ =	5	l_i⁽⁰⁾ =	v₃+l_i⁽⁰⁾=	5
∞	∞	∞
∞	∞	∞
∞	∞	∞
1	∞	∞
∞	∞	∞

v₄ =	5	l_i⁽⁰⁾ =	v₄+l_i⁽⁰⁾=	5
∞	∞	∞
∞	∞	∞
∞	∞	∞
2	∞	∞
∞	∞	∞

v₅ =	2	l_i⁽⁰⁾ =	v₅+l_i⁽⁰⁾=	2
∞	∞	∞
∞	∞	∞
∞	∞	∞
∞	∞	∞
∞	∞	∞

v₆ =	12	l_i⁽⁰⁾ =	v₆+l_i⁽⁰⁾=	12
∞	∞	∞
∞	∞	∞
∞	∞	∞
∞	∞	∞
∞	∞	∞

l_i⁽¹⁾ =	0	v₂ =	∞	l_i⁽¹⁾+v₂=	∞
∞	∞	∞
5	2	∞
5	2	∞
2	∞	∞
12	∞	∞

l_i⁽¹⁾ =	0	v₃ =	5	l_i⁽¹⁾+v₃=	5
∞	∞	∞
5	∞	∞
5	∞	∞
2	1	∞
12	∞	∞

l_i⁽¹⁾ =	0	v₄ =	5	l_i⁽¹⁾+v₄=	5
∞	∞	∞
5	∞	∞
5	∞	∞
2	2	∞
12	∞	∞

l_i⁽¹⁾ =	0	v₅ =	2	l_i⁽¹⁾+v₅=	2
∞	∞	∞
5	∞	∞
5	∞	∞
2	∞	∞
12	∞	∞

l_i⁽¹⁾ =	0	v₆ =	12	l_i⁽¹⁾+v₆=	12
∞	2	∞
5	∞	∞
5	∞	∞
2	∞	∞
12	∞	∞

l_i⁽³⁾ =	0	v₆ =	12	l_i⁽¹⁾+v₆=	12
5	2	7
3	∞	∞
4	∞	∞
2	∞	∞
9	∞	∞

l_i⁽²⁾ =	0	v₂ =	∞	l_i⁽³⁾+v₂=	∞
7	∞	∞
3	2	5
4	2	6
2	∞	∞
12	∞	∞

l_i⁽¹⁾ =	0	v₃ =	5	l_i⁽³⁾+v₃=	5
∞	∞	∞
5	∞	∞
5	∞	∞
2	1	3
12	∞	∞

l_i⁽⁰⁾ =	0	v₅ =	2	l_i⁽³⁾+v₅=	2
∞	∞	∞
∞	∞	∞
∞	∞	∞
∞	∞	∞
∞	∞	∞