КМиИсО

Присваиваем постоянную метку вершине d. Величину l(d) определяет как дуга (c; d), òàê è äóãà (a; d). Поэтому можно окрасить любую из этих дуг. Например, пусть это будет (c; d).

5. Присваиваем вершине d постоянную метку. l(d) = 6

a	3
	b
4	2
7
	2
s	t
3	2
c	3
	d

Òàê êàê t еще не имеет постоянной метки, повторяем Шаг 2.

Производим перерасчет меток (это нужно сделать только для вершины t) l0(t) = minfl0(t); l(d) + l(d; t)g = minf1; 6 + 2g = 8

l0(b) = 7

Присваиваем вершине b постоянную метку и таким образом l(b) = 7. Здесь снова есть два кратчайших пути из s â b: ïî äóãå (s; b) è ïî öåïè

s ! a ! b: Можно выбирать любые из них, например, дугу (s; b).

Так как вершина t не получила постоянную метку, повторяем Шаг 2. 6. l0(b) = 7

Осталось пересчитать только метку вершины t.

11

a	3
	b
4	2
7
	2
s	t
3	2
c	3
	d

l0(t) = minfl0(t); l(b) + l(b; t)g = minf8; 7 + 2g = 8:

Теперь постоянную метку получает вершина t, à äóãà (d; t) становится окрашенной.

a	3
	b
4	2
7
	2
s	t
3	2
c	3
	d

Таким образом, построено дерево кратчайших путей из s, включающее и кратчайший (s; t)- ïóòü:

(s; t) = f(s; c); (c; d); (d; t)g;

длина которого равна 8.

Замечание 1. Решение в общем случае не является единственным. Крат- чайший путь является единственным только в том случае, если в алгоритме ни разу не возникает неоднозначности в выборе дуг. В данном примере такая неоднозначность возникла и одно из соответствующих альтернативных

12

решений - есть:

(s; t) = f(s; a); (a; d); (d; t)g

Замечание 2. Описанный выше алгоритм Дийкстры предполагает неотрицательность длин дуг в заданном графе и не применим к графам, в которых есть отрицательные длины (веса) дуг. Чтобы в этом убедиться, достаточно рассмотреть следующий пример.

a

2 2

s t

1

Решая его по алгоритму Дийкстры, получаем, что кратчайший (s; t)- ïóòü åñòü

(s; t) = f(s; t)g

и его длина равна 1. В действительности же, как легко видеть, таким является путь f(s; a); (a; t)g с нулевой длиной.

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

Модифицированный алгоритм Дийкстры.

1.На Шаге 2 перерасчет величин l(u) производится для всех вершин u, а не только для тех, которые имеют временную метку.

2.Если для некоторой вершины u величина l(u) уменьшается, то ее метка снова становится временной.

3.Процедура продолжается до тех пор, пока все вершины не получат постоянные метки и ни одно из чисел l(u) больше не будет меняться.

Пример

Рассмотрим пример, приведенный в Замечании 2.

Øàã 1.

l(s) = 0; l0(a) = l0(t) = 1

13

Шаг 2. Перерасчитаем метки l0(u).

l0(a) = minfl0(a); l(s) + l(s; a)g = minf1; 0 + 2g = 2; l0(t) = minfl0(t); l(s) + l(s; t)g = minf1; 0 + 1g = 1;

Присваиваем вершине t постоянную метку l(t) = 1 и окрашиваем дугу (s; t)

a

2 2

s	t
	1

Òàê êàê a не имеет постоянной метки, то перерасчитываем метки l0( ) для всех . Так как из вершины t дуг не выходит, то метки не меняются.

Выбираем min по вершинам, не имеющим постоянных меток, в результате чего присваиваем вершине a метку l0(a) = 2 и окрашиваем дугу (s; a).

a

2 2

s t

1

Опять производим перерасчет.

l0(t) = minfl0(t); l(a) + l(a; t)g = minf1; 2 2g = 0;

Для вершины t метка l(t) уменьшилась, поэтому снимаем с дуги (s; t) окраску.

a

22

s t

1

Опять пересчитываем из вершины a метки, в результате чего окрашиваем дугу (a; t) и присваиваем вершине t метку l0(t) = 0:.

14

a

2 2

s t

1

Опять пересчитываем метки. Метки не меняются, следовательно, алгоритм завершил работу и кратчайший путь построен:

(s; t) = f(s; a); (a; t)g:

Замечание 4. Модифицированный алгоритм Дийкстры не решает рассматриваемую задачу при наличии в исходном графе цикла, имеющего отрицательную длину. Действительно, проходя вдоль данного цикла неограни- ченное число раз, можно сделать длину пути сколь угодно малой по величине

15

3 Нахождение кратчайших цепей между всеми парами узлов в сети. Алгоритм Флойда.

3.1Постановка задачи

Постановка задачи. Пусть задан ориентированный граф G = (V; E), каждая дуга e которого имеет длину l(e).Требуется для каждой пары вершин u; 2 V найти кратчайший (u; )-маршрут и его длину. Для решения данной

задачи лучше использовать алгоритм Флойда.

Замечание. Будем рассматривать только графы, в которых нет циклов отрицательной длины. В противном случае (см. Замечание 4 предыдущего параграфа) для некоторых пар вершин не будет существовать кратчайших путей.

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

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

Пусть G = (V; E), множество V = f1; 2; :::ng - множество вершин графа G. Будем строить две последовательности матриц Lp è Sp размера n n; ãäå

p = 0; 1; :::; n.

При этом каждый элемент `pij матрицы Lp- это длина кратчайшего (i; j)- маршрута с промежуточными вершинами от 1 äî p, spij-номер следующей за

i вершины в этом маршруте.

Матрица Lp называется матрицей расстояний, а Sp -справочной матрицей. Шаг 0: Алгоритм начинает работу с L0 = (`0ij)n n ,ãäå

		ij			1; если в графе нет дуги(i; j)
		`0	=		`(i; j); åñëè(i; j) 2 E
è S0 = (s0 )	n n	, ãäå s0	= j. После построения матриц L0 è S0 будем находить
ij		ij
Lp è Sp для каждого p				= 1; 2; :::; n, используя для вычислений элементы

соответствующих матриц, полученных на предыдущих итерациях.

16

Замечание 1.

ìåíò `nij

Шаг 1: Пусть матрицы Lp = (`pij)n n è Sp = (spij)n n найдены. Выделим элементы (p + 1)-й строки и (p + 1)-го столбца матрицы Lp. Назовем эти

множества элементов базовой строкой и базовым столбцом соответственно. Шаг 2: Построим матрицы Lp+1 è Sp+1, исходя из следующего правила:

äëÿ i 6= p + 1; j 6= p + 1

Åñëè `pij > `pip+1 + `pp+1j, òî `pij+1 := `pip+1 + `pp+1j è spij+1 = spip+1. Åñëè `pij `pip+1 + `pp+1j, òî `pij+1 := `pij è spij+1 = spij.

Åñëè p + 1 = n, алгоритм заканчивает свою работу, если p + 1 < n; переходим к Шагу 2.

Теорема 3.1 Если в графе нет циклов отрицательной длины, то эле- матрицы Ln равен длине кратчайшего (i; j)-пути.

Åñëè `pip = 1,ò.å. i-й элемент базового столбца равен 1, òî äëÿ i-й строки Шаг 2 выполнять не нужно.

Åñëè `ppj = 1, ò.å. j-й элемент равен 1,то не нужно выполнять Шаг 2 для

элементов j- го столбца.
	p+1	p	p+1	p
Замечание 2. Элементы							n; òî åñòü ýëå-
	`ip+1	= `ip+1; `pnj		= `pnj	; 8i; j = 1;неизменными.
менты базовой строки и столбца переносятся в матрицу						Lp+1
3.3 Пример
Найти кратчайшие цепи для всех пар узлов в сети:
		2
	8			6
		3		3
					3
1
		4	7	2
	5
1				3
			4
	5	1

17

Решение:

Составляем матрицы L0 = (`0ij)5 5 è S0 = (s0ij)5 5

0	0	1	1	1			7	1		1
	B	1	8	3			4 1			C
		5			2				1
	B	1		1				1		C
L =	B		6				3			C
			1				1
	B	1	3	1		1				C
	@							1 A

0		0	1	2	3	4	5	1
		B	1	2	3	4	5	C
S	=		1	2	3	4	5
		B	1	2	3	4	5	C
		B						C
		B	1	2	3	4	5	C
		@						A

Итерация 1.

Óçåë p = 1 определяется как базовый. Выделяем в матрице L0 первую

строку и первый столбец. Кроме того, строки 2, 3 и 5 в базовом столбце содержат элементы, равные 1, и, следовательно, эти строки не изменятся.

Поэтому, для того чтобы посчитать матрицу L1, следует исследовать лишь элементы 4-é строки матрицы L0, показанные на рисунке вместе с базовыми строкой и столбцом:

0	0	1	8 3	4 1		1
	B	1				C
		5	2		1
	B	1				C
L =	B		1	1		C
	B					C
	@	1				A

18

Применяя к этим элементам алгоритм Флойда, получаем следующие матрицы:

1		0	1 1 1						7		1		1
		B	1	8		3		4			1		C
			5	13			2		1			1
		B	1 6			1					1		C
L =		B							3				C
				3
		B	1			1							C
		@						1 1 A
Здесь `421 = minf`420 ; `411 + `121 g = minf1; 5										+ 8g = 13; `441 = minf`440 ; `410 +
`140 g = 1:
Тогда			0								1
				1	2	3		4		5
	S1 = B			1	2	3		4		5	C
				1	2	3		4		5
			B								C
			B								C

BC

@	1	1	3	1	5	A
	1	2	3	4	5

(Здесь s142 = s041; s144 = s041, а остальные элементы матрицы S1 остаются прежними, так как не изменились элементы матрицы L0.)

Итерация 2.

Рассмотрим p = 2. Выделяем вторую строку и второй столбец в матрице L1 и переписываем их без изменений. На рисунке, кроме элементов базовой строки и столбца, показаны элементы, которые нужно пересчитать:

0	0	1 1 1	7	1	1
L = B		8	4		C
		13	1
	B	6	3		C
	B				C
	B				C
	@	3	1		A

19

Используя алгоритм Флойда, получаем матрицы:

2		0	1 1 1							7	1		1
		B	1		8		3		4		1		C
				5	13			2		1		1
		B	1 6				1				1		C
L =		B								3			C
					3				10
		B	1				1						C
		@									1 A
		2		0	1	2	3		4	5	1
				B	1	2	3		4	5	C
					1	1	3		1	5
	S =			B	1	2	3		4	5	C
				B							C
				B	1	2	3		2	5	C
				@							A

Далее, действуя аналогично, получаем:

3	0	1 1 1				7	1		1
	B	1	8	3		4	1		C
		5	4		2	1		1
	B	1		1			1		C
L =	B		6			3			C
			3			10
	B	1		1					C
	@						1 A

3		0	1	2	3	4	5	1
		B	1	2	3	4	5	C
S	=		1	3	3	1	5
		B	1	2	3	4	5	C
		B						C
		B	1	2	3	2	5	C
		@						A

4	0	12	11	5		7	6		1
	B	1	0	6		4	5		C
L =		5	4		2	1		1
	B								C
	B	8	6	1		3	2		C
		15	3			10
	B			8			9		C
	@								A

20