(№ 1189) (О. Щецова) Между населёнными пунктами А, В, С, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами А и G, проходящего через пункт Е (при условии, что передвигаться можно только по построенным дорогам).

	A	B	C	D	E	F	G
A		2			5
B	2		4	2	3
C		4					6
D		2					9
E	5	3				5	14
F					5		7
G			6	9	14	7

Для решения этой задачи нам нужно найти кратчайший путь из пункта A в пункт G, обязательно проходящий через пункт E. Мы рассмотрим все возможные пути и выберем самый короткий.

Шаг 1: Находим кратчайшие пути из A в E.

• A -> E: Длина пути равна 5.

Шаг 2: Находим кратчайшие пути из E в G.

• E -> G: Длина пути равна 14.

Шаг 3: Анализируем возможные пути из A в G через E, используя таблицу расстояний.

Мы уже знаем кратчайшие пути A -> E и E -> G. Теперь сложим эти пути, чтобы получить общий путь A -> E -> G.

Шаг 4: Вычисляем общую длину пути A -> E -> G.

• Длина пути A -> E -> G = Длина(A -> E) + Длина(E -> G) = 5 + 14 = 19.

Шаг 5: Проверяем, есть ли другие пути из A в G через E, которые могут быть короче.

Путь A -> B -> E -> G:

• A -> B = 2
• B -> E = 3
• E -> G = 14
• Общая длина = 2 + 3 + 14 = 19

Путь A -> E -> F -> G:

• A -> E = 5
• E -> F = 5
• F -> G = 7
• Общая длина = 5 + 5 + 7 = 17

Вывод:

Сравнивая длины всех возможных путей через E, мы видим, что самый короткий путь - A -> E -> F -> G с длиной 17.

Ответ: 17