1. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

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

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

Проверить

Посмотреть пояснение и ответ

A–B–C–D: 7; A–C–D: 8; A–E–D: 8. Кратчайший путь — 7.
Ответ: 7

2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.

	A	B	C	D	E	F
A		3				15
B	3		2	3	7
C		2		1	3
D		3	1		1
E		7	3	1		2
F	15				2

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

Проверить

Посмотреть пояснение и ответ

Общий маршрут: A — B — C — D — E — F. Длина: 5 (A–C) + 4 (C–F) = 9.
Ответ: 9

3. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

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

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

Проверить

Посмотреть пояснение и ответ

Самый короткий путь проходит через пункты D и C. Его длина равна 6.
Ответ: 6

4. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.

	A	B	C	D	E	F
A		3	5			15
B	3			4
C	5			3
D		4	3		2	6
E				2		2
F	15			6	2

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

Проверить

Посмотреть пояснение и ответ

A–F: 15; A–B–D–E–F: 11; A–C–D–E–F: 12. Кратчайший путь равен 11.
Ответ: 11

5. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.

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

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

Проверить

Посмотреть пояснение и ответ

Самым выгодным маршрутом будет A → B → D → F. Его длина: 2 (A–B) + 2 (B–D) + 6 (D–F) = 10.
Ответ: 10