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

Решение:

Нам нужно найти кратчайший путь из А в В, проходящий через D. Это означает, что путь будет иметь вид A → ... → D → ... → B.

Сначала найдём кратчайший путь из A в D, а затем из D в B.

1. Кратчайший путь из A в D:

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

• A → B → D: 2 + 8 = 10
• A → C → D: 4 + 3 = 7
• A → D: (нет прямого пути, только через другие пункты)

Кратчайший путь из A в D равен 7.

2. Кратчайший путь из D в B:

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

• D → B: 8
• D → C → B: 3 + 4 = 7
• D → E → B: 3 + 1 = 4
• D → F → B: 6 + 2 = 8

Кратчайший путь из D в B равен 4 (через E).

3. Общий кратчайший путь A → D → B:

Складываем кратчайший путь из A в D и кратчайший путь из D в B:

7 (A → C → D) + 4 (D → E → B) = 11.

Примечание: Путь A → C → D → E → B.

Ответ: 11