3.7. Задачи для самостоятельной работы

3.7.1. Определить кратчайший путь во взвешенном графе с помощью волнового алгоритма. Граф задан матрицей смежности, элемент матрицы задаёт вес соответствующей дуги. Во всех заданиях номер варианта выбирается по формуле n = N mod 6 + 1.

1	x1	x2	x3	x4	x5	x6	x7	x8		2	x1	x2	x3	x4	x5	x6	x7	x8
x1		2	3	5			4			x1		3	3	2			5
x2					2		1			x2					4		2
x3					3	4				x3					1	5
x4						4	2			x4						1	5
x5								6		x5								4
x6								4		x6								2
x7								4		x7								5
x8										x8

3	x1	x2	x3	x4	x5	x6	x7	x8		4	x1	x2	x3	x4	x5	x6	x7	x8
x1		2	3	3			4			x1		4	4	3			2
x2					3		4			x2					2		2
x3					2	3				x3					3	1
x4						1	3			x4						4	2
x5								3		x5								5
x6								2		x6								3
x7								5		x7								4
x8										x8

17

1)(X2,X4)(X4,X5)(X5,X1)(X1,X3);

2)(X3,X5)(X5,X1)(X1,X2)(X2,X3);

3)(X3,X4)(X4,X5)(X5,X1)(X1,X2)(X2,X3).