Минимальный разрез (R, R′) является «узким местом» сети. Найдем его пропускную способность:

′	= d12 + d34 = 7 + 7 = 14	3	/ч),
C( R, R ) = ∑dij		(м
′
uij (R,R )

что совпадает с величиной максимального потока воды в водопроводе.

Проведем анализ сети. Проверим условие сохранения потока на примере 2-й вершины. Известно, что в промежуточных вершинах пути потоки не создаются и не исчезают, т.е.

∑xi2 −∑x2 j = 0 .

i j

Действительно, (х12 + х42) −( х23 + х24 + х25) = (7 + 0) − (0 + 0 + 7) = = 0 (м3/ч).

Покажем также, что общее количество воды, вытекающей из источника I (из водонапорной башни), совпадает с общим количеством воды, поступающей в сток S (на ферму), т.е.

− ∑xiI + ∑xIj = ∑xiS −∑xSj = zmax i j i j

− 0 + (х12 + х14) = (х25 + х45) − 0 7 + 7 = 7 + 7 = 14 (м3/ч).

2.7. Задача о кратчайшем пути на графе. Алгоритм Дийкстры

Рассмотрим взвешенный граф G(V, U) без петель и контуров, любой дуге uij = (i, j) U которого поставлено в соответствие

число lij , называемое длиной (в общем случае, весом). Если граф

содержит ребра, то любое из них можно заменить на пару противоположно ориентированных дуг с той же длиной. Требуется найти

пути из выделенной вершины v0 V во все остальные вершины графа, длина (или суммарный вес) каждого из которых минимальна.

110

Пусть для любой вершины vi V графа G(V, U) элементы l*(i),

v*(i) означают длину и предпоследнюю вершину кратчайшего пути из источника I в вершину vi, а элементы l(i), v(i) – длину и предпоследнюю вершину некоторого (не обязательно кратчайшего) пути. Пару (l(i), v(i)) назовем временной меткой, а пару (l*(i), v*(i)) – постоянной меткой. Обозначим через R множество помеченных вершин. Алгоритм Дийкстры заключается в том, что на любой итерации одна очередная вершина vi присоединяется к множеству помечен-

ных вершин R и получает постоянную метку (l*(i), v*(i)), которая в дальнейшем не меняется. А для остальных вершин j R (т.е. для j V\R) пересматриваются текущие значения длин l(j). Результаты вычислений на всех итерациях заносятся в таблицу. Рассмотрим алгоритм Дийкстры построения дерева кратчайших путей на примере.

Пример 13. Туристическая фирма организовывает экскурсионные туры на автобусе с посещением ряда городов зарубежья (v1, v2, v3, v4, v5, v6, v7) (рис. 2.16). Выезд планируется из Минска (v0). Требуется найти кратчайшие пути из Минска в эти города, если известны расстояния между городами (в тыс. км).

	v1		6						v4	4
	2	3	4		3
v0				1					5		v7
		v2
	4					v5		1
		2	5							2
	1
	v3								v6
					4
					Рис. 2.16

Решение. Составим математическую модель задачи. Вершины графа можно интерпретировать как пересечение дорог, а ребра – как участки дорог, связывающих вершины. Любому ребру можно поставить в соответствие длину данного участка дороги в километрах. Тогда задача сведется к нахождению кратчайшего пути из вершины v0 (Минска) во все остальные вершины графа. Расставлять метки на рис. 2.17 и заполнять табл. 2.8 будем по ходу алгоритма Дийкстры.

111

Рис. 2.17

Таблица 2.8

Вершина	v0		v1		v2	v3	v4	v5	v6	v7
Метка,	l(0),	l(1),			l(2),	l(3),	l(4),	l(5),	l(6),	l(7),
итерация	v(0)	v(1)			v(2)	v(3)	v(4)	v(5)	v(6)	v(7)
1	0 ,v0	2, v0			4, v0	1, v0	∞, v0	∞, v0	∞, v0	∞, v0
2		2, v0			3, v3	1 ,v0	∞, v0	6, v3	5, v3	∞, v0
3					3, v3		8, v1	6, v3	5, v3
		2		,v0				6, v1		∞, v0
4					3 ,v3		8, v1	4, v2	5, v3	∞, v0
5							7, v5	4 ,v	5, v3	9, v5
								2	5, v5
									5 ,v
6							7, v5		3	7, v6
									5 ,v
									5
7							7 ,v			7, v6
							5
8										7 ,v6

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

1. Так как все пути будут выходить из вершины v0, ее сразу помечают, т.е. присваивают

l(0):= 0*, v(0):= v0 , R:= {v0}.

112

min

j V \ R

2. Для остальных вершин j ≠ v0 определяют длину l(j) по формуле

l( j) := lv0 j , если(v0 , j) U;∞, если(v0 , j) U,

и указывают предпоследнюю вершину пути:

v( j) := v0 .

Таким образом, в табл. 2.8 заполняют первую строку:

l(1):= 2, так как (v0, v1) U, v(1):= v0;

l(4):= ∞, поскольку (v0, v4) U, v(4):= v0 и т.д.

3. Из непомеченных вершин находят номер i V\R, для которого достигается минимум l( j) = l(i) .

В нашем примере min {l(1), l(2),…, l(7)} = l(3) = 1.

4. Если l(i) = ∞ (т.е. минимум равен ∞) и множество помеченных

вершин не совпадает с множеством V (т.е. R ≠ V), то алгоритм заканчивает свою работу. В вершины, не имеющие постоянной метки, не существует пути из выделенной вершины v0. Иначе переходят к пункту 4.

5. Если l(i) < ∞ (т.е. минимум конечен), то полагают

i:= vi , R: = R { vi }, l(i):= l*(i), v(i):= v*(i).

В данном примере i:= v3, R:= R {v3} = {v0, v3}, l(3):= 1*, v(3):= v0*.

6.Если R = V (или i = S), то найдены все кратчайшие пути во все вершины графа. Алгоритм заканчивает свою работу. Иначе переходят к пункту 7.

7.Если R ≠ V (или i ≠ S), то рассматривают дуги (i, j) U, которые существуют, т.е. i R, j V\R. Полагают

l(j):= min{l*(i) + lij ; l(j)},

113

где l*(i) – постоянная метка вершины vi (начала дуги), lij – длина дуги ( vi , vj ), l(j) – временная метка вершины vj (конца дуги).

Если l*(i) + lij < l(j), то присваивают v(j):= vi , иначе временная метка v(j) вершины vj не меняется. Незаполненные клетки данной

строки переписывают из соответствующих столбцов. Переходят к пункту 2.

В табл. 2.8 заполняют вторую строку. Для этого находят дуги с началом в последней отмеченной вершине, а с концом – в неотмеченной. В нашем примере это дуги с началом в вершине v3: (v3, v2), (v3, v5) (v3, v6). Для них считают l(2), l(5), l(6) соответственно:

(v3,v2): l(2):= min{l*(3) + l32; l(2)} = min{1 + 2;4} = 3, v(2):= v3; (v3,v5): l(5):= min{l*(3) + l35; l(5)} = min{1 + 5;∞} = 6, v(5):= v3; (v3,v6): l(6):= min{l*(3) + l36; l(6)} = min{1 + 6; ∞} = 7, v(6):= v3.

Аналогично заполняют третью строку табл. 2.8:

а) пункт 3 алгоритма: l(1):= min{l(1), l(2), l(4),…, l(7)} = 2;

б) пункт 5 алгоритма: i:= v1, R:= R {v1} = {v0, v1, v3}, l(1):= 2*, v(1):= v0 ;

в) пункт 7 алгоритма: находят дуги с началом в вершине v1 ((v1, v2), (v1, v5) (v1, v4)) и вычисляют l(2), l(5), l(4) соответственно:

(v1, v2): l(2):= min{l*(1) + l12; l(2)} = min{2 + 3;3} = 3, значит, v(2)

не меняется;

(v1, v5): l(5):= min{l*(1) + l15; l(5)} = min{2 + 4;6} = 6, значит, v(5):= {v1, v3};

(v1, v4): l(4):= min{l*(1) + l14; l(4)} = min{2 + 6; ∞} = 8, v(4):= v1.

Незаполненные клетки переписываются из второй строки. Остальные строки заполняются аналогично.

Замечание. Число l*(i) постоянной метки вершины vi равно длине кратчайшего пути из выделенной вершины v0 в вершину νi, а сам путь восстанавливается последовательным просмотром постоянных меток v*(i) предпоследних вершин в кратчайшем пути.

114

В данном примере выпишем кратчайшие пути из вершины v0 во все остальные вершины графа:

v0→v7: v0 – v3 – v2 – v5 – v6 – v7, l*(7) = 7 (тыс. км);

v0→v6: v0 – v3 – v2 – v5 – v6 или v0 – v3 – v6, l*(6) = 5 (тыс. км); v0→v5: v0 – v3 – v2 – v5, l*(5) = 4 (тыс. км);

v0→v4: v0 – v3 – v2 – v5 – v4, l*(4) = 7 (тыс. км); v0→v3: v0 – v3, l*(3) = 1 (тыс. км);

v0→v2: v0 – v3 – v2, l*(2) = 3 (тыс. км); v0→v1: v0 – v1, l*(1) = 2 (тыс. км).

Так, отправляясь в город v6, туристическая фирма в целях посещения наибольшего числа городов предпочтет маршрут v0 – v3 – v2 –

– v5 – v6, хотя на обратной дороге можно сразу следовать в город v3, при этом наименьшее расстояние не изменится.

115