1.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		1
B	1		2	2	7
C		2			3
D		2			4
E		7	3	4

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем в "В" 

из "В" мы попадаем в "С", "Д", "Е"=> Самые короткие пути "С" и "Д"( по 2)

Из "С" мы можем попасть сразу в "Е" => Сравним "СЕ" и "ДЕ"

1) "СЕ": 2+3=5

2) "СД": 2+4= 6

Выбираем дорогу "СД"

Ответ: "АВСЕ"= длина кратчайшего маршрута: 6

2.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		5	3
B	5		1	4
C	3	1		6
D		4	6		1
E				1

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем в "В" (5) и в "С" (3).

Из "В" мы попадаем в "С" (1) и в "D" (4).
Из "С" мы попадаем в "D" (6).
Из "D" мы попадаем в "E" (1).

Рассмотрим возможные пути:

1. "А-В-D-E": 5 + 4 + 1 = 10

2. "А-С-D-E": 3 + 6 + 1 = 10

3. "А-С-В-D-E": 3 + 1 + 4 + 1 = 9

Самый короткий путь: "А-С-В-D-E" длиной 9.

Ответ: длина кратчайшего маршрута: 9.

3.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		3	7
B	3		2		8
C	7	2		4
D			4		1
E		8		1

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем в "В" (3) и в "С" (7).

Из "В" мы попадаем в "С" (2) и в "E" (8).
Из "С" мы попадаем в "D" (4).
Из "D" мы попадаем в "E" (1).

Рассмотрим возможные пути:

1. "А-В-E": 3 + 8 = 11

2. "А-В-С-D-E": 3 + 2 + 4 + 1 = 10

3. "А-С-D-E": 7 + 4 + 1 = 12

Самый короткий путь: "А-В-С-D-E" длиной 10.

Ответ: длина кратчайшего маршрута: 10.

4.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		1
B	1		4	2	8
C		4			4
D		2			4
E		8	4	4

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем только в "В" (1).

Из "В" мы попадаем в:

"С" (4)

"D" (2)

"E" (8)

Из "С" и "D" мы попадаем в "E" (по 4).

Рассмотрим возможные пути:

1. "А-В-E": 1 + 8 = 9

2. "А-В-D-E": 1 + 2 + 4 = 7

3. "А-В-С-E": 1 + 4 + 4 = 9

Самый короткий путь: "А-В-D-E" длиной 7.

Ответ: длина кратчайшего маршрута: 7.

5.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		4	7
B	4		1	5
C	7	1		3
D		5	3		1
E				1

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем в "В" (4) и в "С" (7).

Из "В" мы попадаем в:

"С" (1)

"D" (5)

Из "С" мы попадаем в "D" (3).
Из "D" мы попадаем в "E" (1).

Рассмотрим возможные пути:

1. "А-В-D-E": 4 + 5 + 1 = 10

2. "А-В-С-D-E": 4 + 1 + 3 + 1 = 9

3. "А-С-D-E": 7 + 3 + 1 = 11

Самый короткий путь: "А-В-С-D-E" длиной 9.

Ответ: длина кратчайшего маршрута: 9.

6.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		7	4
B	7		2		4
C	4	2		4
D			4		4
E		4		4

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем в "В" (7) и в "С" (4).

Из "В" мы попадаем в:

"С" (2)

"E" (4)

Из "С" мы попадаем в "D" (4).
Из "D" мы попадаем в "E" (4).

Рассмотрим возможные пути:

1. "А-С-E": 4 + (через D) 4 + 4 = 12

2. "А-С-В-E": 4 + 2 + 4 = 10

3. "А-В-E": 7 + 4 = 11

4. "А-С-D-E": 4 + 4 + 4 = 12

Самый короткий путь: "А-С-В-E" длиной 10.

Ответ: длина кратчайшего маршрута: 10.

7.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		3
B	3		1	2	6
C		1			3
D		2			3
E		6	3	3

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем только в "В" (3).

Из "В" мы попадаем в:

"С" (1)

"D" (2)

"E" (6)

Из "С" и "D" мы попадаем в "E" (по 3).

Рассмотрим возможные пути:

1. "А-В-E": 3 + 6 = 9

2. "А-В-С-E": 3 + 1 + 3 = 7

3. "А-В-D-E": 3 + 2 + 3 = 8

Самый короткий путь: "А-В-С-E" длиной 7.

Ответ: длина кратчайшего маршрута: 7.

8.

Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

	A	B	C	D	E
A		2	5	1
B	2		3
C	5	3		3	2
D	1		3
E			2

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяженность которых указана в таблице.

Решение:

Из "А" мы попадаем в:

"В" (2)

"С" (5)

"D" (1)

Из "В" мы попадаем в "С" (3)
Из "С" мы попадаем в "E" (2)
Из "D" мы попадаем в "С" (3)

Рассмотрим возможные пути:

1. "А-С-E": 5 + 2 = 7

2. "А-В-С-E": 2 + 3 + 2 = 7

3. "А-D-С-E": 1 + 3 + 2 = 6

Самый короткий путь: "А-D-С-E" длиной 6.

Ответ: длина кратчайшего маршрута: 6.