Волновой алгоритм построения кратчайшего пути

для взвешенного графа

Алгоритм называется волновым, так как от рассматриваемой вершины исходит виртуальная волна, которая захватывает смежные с ней вершины.

1. Вершина x_Н получает вес V_Н =0, её номер вводится в массив М номеров вершин, изменивших вес. Остальные вершины x_i получают вес V_i =¥ и их номера не попадают в массив M.

2. Если массив М пуст, то выполняется п. 3, иначе выбирается с исключением из него очередная вершина x_i и пересчитываются веса вершин, принадлежащих исходу E(x_i) вершины x_i: " x_i Î X ½ V_j= min (V_j, V_i+ l_ij)). Если вес V_i уменьшается, то номер j включается с приведением подобных в М. Снова выполняется п. 2.

3. Если вес V_K =¥, то делается вывод, что пути из вершины x_н к вершине x_K нет, иначе переход к п. 4.

4. Выполняется процедура выделения дуг, которая заключается в следующем. Выделяем текущую вершину x_i, начиная с конечной, и записываем множество всех вершин, смежных с текущей: E^-1(x_i)={x_j,x_m…}; здесь номера вершин упорядочены по возрастанию. Затем последовательно для каждой вершины из множества E^-1(x_i) определяем вес дуги как разность весов вершин, текущей x_i и рассматриваемой x_j. Если V_i-V_j=l_ij, где l_ij - вес дуги, а V_i, V_j – веса вершин, вычисленные на первом проходе (окончательные значения!), то эта дуга является фрагментом одного из кратчайших путей. Далее x_j полагаем текущей вершиной и переходим на начало этой процедуры. Процедура заканчивается при достижении начальной вершины.

Отметим, что в волновом алгоритме для невзвешенного графа разность весов вершин x_j и x_i должна быть равна 1.

5. После выделения дуг строятся кратчайшие пути, длины которых равны V_k.

Обратите внимание на то, что алгоритм выполняется в 3 прохода. На 1-м проходе (это п. 2 словесного описания алгоритма – СОА) вычисляются и пересчитываются веса всех вершин, включая конечную (x_K = x₆). На 2-м проходе (это п. 4 СОА) выявляютя «претенденты» на кратчайший путь, т.е. дуги, которые могут составить этот путь (эти пути, поскольку их может оказаться несколько с одинаковым весом). На 3-м проходе (это п. 5 СОА) из дуг-претендентов составляются конкретные кратчайшие пути. Задача составления пути из дуг-претендентов является переборной. Здесь важно учесть все возможные варианты перебора.

Пример 3.2. Найти кратчайший путь во взвешенном графе (рис.3.2).

Кратко запишем процесс решения задачи(* отмечается дуга, являющаяся претендентом на включение в кратчайший путь)

1. V_Н = V₁ =0, V₂ = V₃ =…= V₆ = V_k = ¥, М ={1}.

2. M ¹Æ, i =1, M =Æ, E (x₁)={ x₂, x₃ }; V₂ =min(¥, 0+1)=1; M ={2}.

V₃ =min(¥, 0+4)=4; M ={2, 3}.

2. M ¹Æ, i =2, M ={3}, E (x₂)={ x₃, x₄ }; V₃ =min(4, 1+2)=3; M ={3}.

V₄ =min(¥, 1+5)=6; M ={3, 4}.

2. M ¹Æ, i =3, M ={4}, E (x₃)={ x₄, x₅ }; V₄ =min(6, 3+2)=5; M ={4}.

V₅ =min(¥, 3+4)=7; M ={4, 5}.

 

	2. M ¹Æ, i =4, M ={5}, E (x4)={ x5, x6 }; V5 =min(7, 5+1)=6; M ={5}. V6 =min(¥, 5+4)=9; M ={5, 6}. 2. M ¹Æ, i =5, M ={6}, E (x5)={ x6 }; V6 =min(9, 6+2)=8; M ={6}. 2. M ¹Æ, i =6, M =Æ, E (x5)=Æ;

3. V_К ¹¥, переход к п.4.

4. E^{- 1}(x₆)={ x₄, x₅ }; V ₆ - V₅ = 2, l_5,6 = 2 *; V ₆ - V₄ = 3, l_4,6 = 4.

E^{- 1}(x₅)={ x₃, x₄ }; V₅ - V₄ = 1, l_4,5 = 1 *; V₅ - V₃ = 3, l_5,3 = 4.

E^{- 1}(x₄)={ x₂, x₃ }; V₄ - V₃ = 2, l_3,4 = 2 *; V₄ - V₂ = 4, l_2,4 = 5.

E^{- 1}(x₃)={ x₁, x₂ }; V₃ - V₂ = 2, l_2,3 = 2 *; V₃ - V₁ = 3, l_1,3 = 4.

E^{- 1}(x₂)={ x₁ }; V ₂ - V₁ = 1, l_1,2 = 1 *;

Процесс решения на 1-ом проходе алгоритма можно оформить в виде таблицы (табл. 3.3).

На обратном проходе выделяемпретендентов. Из них на 3-м проходе строим путь длиной 8.Кратчайший путь(xН,xК)включает в себя дуги (xН = x1, x2), (x1, x2), (x2, x3), (x3, x4), (x4, x5), (x5, x6 = xК).

Таблица 3.3

X1	X2	X3	X4	X5	X6	M
	¥	¥	¥	¥	¥
	1		¥	¥	¥	2, 3
		3		¥	¥	3, 4
			5		¥	4, 5
				6		5, 6
					8
						Æ