Networks2012-04-Routing

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

2	8	4

6	2

1	2	4	3	6

3	6
	7
3	5

Ицыксон В.М. ТКС © 2012

21

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

O Шаг 1. Начальные условия

O Граф дополняется до полного. Вес новых дуг - ∞.

O h := 0

O Вводится начальная разметка:

	O D(h), 1= 0
	O D(h), i = ∞, i ≠ 1
O Шаг 2. Перерасчет оценок
O	Для всех i: D(h+1), i = minj [D(h), j + ri,j]
O	h := h + 1

O Шаг 3.

O Если h = N – выход

O Если оценки не изменились – выход

O Иначе – переход к шагу 2

Ицыксон В.М. ТКС © 2012

22

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

	Шаг 1
∞		∞
2	8	4

6	2

0

1	2	4	3	6 ∞

3		6
3		7	5
∞			∞
Ицыксон В.М. ТКС © 2012		23

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

∞ 6	∞ ∞

		2			8		4
									2
		6
0
0			2		4			3			∞
	1								6
											∞
		3			7				6
		3					5
									∞ ∞
				∞	3
											24
		Ицыксон В.М. ТКС © 2012

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

∞ 6 5

∞ ∞ 14

		2	8
		6
0		2	4
0
0	1

3

7

3

∞ 3 3

Ицыксон В.М. ТКС © 2012

4

2

3	6	∞
		∞
		∞

6

5

∞∞ 10

25

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

∞ 6 5 5

∞ ∞ 14 13

		2	8
		6
0		2	4
0
0	1
0

3

7

3

∞ 3 3 3

Ицыксон В.М. ТКС © 2012

4

2

3
		6	∞
			∞
			∞
	6		16

5

∞∞ 10 9

26

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

∞	6	5	5 5		∞	∞	14	13	12

		2	8
		6
0		2	4
0
0	1

0

0

3

7

3

∞ 3 3 3 3

Ицыксон В.М. ТКС © 2012

4

2

3	6	∞

∞

∞

6 16

15

5

∞∞ 10 9 9

27

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

∞	6	5	5	5 5		∞	∞	14	13	12	12

			2			8						4
															2
			6
0
0				2		4							3
																				∞
0	1																6
																				∞
0
																				∞
0
			3												6					16
0
						7														15
			3									5
																				14
														∞	∞	10	9	9 9
						∞	3	3	3	3 3
																				28
			Ицыксон В.М. ТКС © 2012

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

∞ 6 5 5 5 5

		2	8	4
		6
0		2	4	3
0
0	1
0
0
0		3	7
		3		5
		∞	3 3 3	3 3

Ицыксон В.М. ТКС © 2012

∞ ∞ 14 13 12 12

2

6 ∞

∞

∞

6 16

15

14

∞∞ 10 9 9 9

29

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

O Общее число операций:

O N – число вершин

O N-1 – число шагов

O N – операций при минимизации на каждом шаге

O W = O(N3)

O Достоинства алгоритма:

O Хорошо распараллеливается O Просто реализуется

O Не требует ресурсов памяти

O Требуется информация только о соседней вершине O Часто заканчивается раньше N-1 итерации

O Недостатки алгоритма:

O В худшем случае количество операций - ~ N3

Ицыксон В.М. ТКС © 2012

30