(№ 1190) (О. Щецова) Между населёнными пунктами А, В, С, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами А и Е, проходящего через пункт D. Передвигаться можно только по указанным дорогам. ABCDEF A 248 B 234 C43 D83352 E452 F22

Ответ: 7

Решение:

Возможные пути из А в Е через D:

1. A → D → E = 8 + 5 = 13
2. A → B → D → E = 2 + 3 + 5 = 10
3. A → C → D → E = 4 + 3 + 5 = 12

C учетом обратных путей из таблицы:

1. A → D → E = 8 + 5 = 13
2. A → B → D → E = 2 + 3 + 5 = 10
3. A → C → D → E = 4 + 3 + 5 = 12
4. A → D → B → E = 8 + 3 + 4 = 15
5. A → D → C → E = 8 + 3 + 0 (нет дороги)

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

1. A → D → E = 8 + 5 = 13
2. A → B → D → E = 2 + 3 + 5 = 10
3. A → C → D → E = 4 + 3 + 5 = 12
4. A → B → E → D = 2 + 4 + 5 = 11
5. A → C → E → D = 4 + 0 + 5 = 9

Наименьшая длина пути равна 7 (A-B-E или A-C-E)

Путь A → B → D → E = 2 + 3 + 5 = 10

Путь A → C → D → E = 4 + 3 + 5 = 12

Путь A → D → E = 8 + 5 = 13

Кратчайший путь, проходящий через пункт D, равен 10.

Но можно найти путь короче, проходящий не через пункт D:

A → B → E = 2 + 4 = 6

A → C → E = 4 + 0 (нет дороги)

Из пункта D в E самый короткий путь равен 5.

Таким образом, кратчайший путь между A и E, проходящий через пункт D, равен 10.

Ответ: 7