Контрольная работа по "Информатике"

1. Задача нахождения кратчайшего  пути

 

 

 

 

 

 

Дана начальная матрица D0:                  начальная матрица S0:

	1	2	3	4	5			1	2	3	4	5
1	-	12	10	∞	∞		1	-	2	3	4	5
2	12	-	∞	15	∞		2	1	-	3	4	5
3	10	∞	-	6	3		3	1	2	-	4	5
4	∞	15	6	-	21		4	1	2	3	-	5
5	∞	∞	3	21	-		5	1	2	3	4	-

 

Шаг 1. В матрице D0 выделены ведущие строка и столбец (k=1).

                матрица D1:                                           матрица S1:

	1	2	3	4	5			1	2	3	4	5
1	-	12	10	∞	∞		1	-	2	3	4	5
2	12	-	22	15	∞		2	1	-	1	4	5
3	10	22	-	6	3		3	1	1	-	4	5
4	∞	15	6	-	21		4	1	2	3	-	5
5	∞	∞	3	21	-		5	1	2	3	4	-

 

 

 

Шаг 2. Полагаем k=2; в матрице D1 выделены ведущие строка и столбец.  В результате получаем матрицы D2 и S2:

                матрица D2:                                           матрица S2:

	1	2	3	4	5			1	2	3	4	5
1	-	12	10	27	∞		1	-	2	3	2	5
2	12	-	∞	15	∞		2	1	-	1	4	5
3	10	∞	-	6	3		3	1	1	-	4	5
4	27	15	6	-	21		4	2	2	3	-	5
5	∞	∞	3	21	-		5	1	2	3	4	-

 

 

Шаг 3. Полагаем k=3; в матрице D2 выделены ведущие строка и столбец.  В результате получаем матрицы D3 и S3:

                матрица D3:                                           матрица S3:

	1	2	3	4	5			1	2	3	4	5
1	-	12	10	16	13		1	-	2	3	3	3
2	12	-	∞	15	∞		2	1	-	1	4	5
3	10	∞	-	6	3		3	1	1	-	4	5
4	16	15	6	-	21		4	3	2	3	-	5
5	13	∞	3	21	-		5	3	2	3	4	-

 

 

 

 

 

Шаг 4. Полагаем k=4; в матрице D3 выделены ведущие строка и столбец.  В результате получаем матрицы D4 и S4:

                матрица D4:                                           матрица S4:

	1	2	3	4	5			1	2	3	4	5
1	-	12	10	∞	∞		1	-	2	3	3	3
2	12	-	21	15	36		2	1	-	4	4	4
3	10	21	-	6	3		3	1	4	-	4	5
4	∞	15	6	-	21		4	3	2	3	-	5
5	∞	36	3	21	-		5	3	4	3	4	-

 

Шаг 5. Полагаем k=5; в матрице D4 выделены ведущие строка и столбец. 

                матрица D4:                                           матрица S5:

	1	2	3	4	5			1	2	3	4	5
1	-	12	10	∞	∞		1	-	2	3	3	3
2	12	-	∞	15	∞		2	1	-	4	4	4
3	10	∞	-	6	3		3	1	4	-	4	5
4	∞	15	6	-	21		4	3	2	3	-	5
5	∞	∞	3	21	-		5	3	4	3	4	-

 

Никаких действий на этом шаге не выполняем, вычисления закончены. Конечные матрицы D4 и S4  содержат всю информацию для определения кратчайших путей между любыми двумя узлами сети.