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

Краткий ответ: 10.

Как решать

1. По таблице выписываем только существующие дороги:

\[ AB=5,\quad AC=9,\quad AD=6,\quad AE=9, \] \[ BD=4,\quad CD=2,\quad CE=2,\quad DE=5. \]

Пустая клетка означает, что дороги нет.

2. Путь должен проходить через \(D\), поэтому его можно разбить на два участка:

\[ A \to \ldots \to D \quad \text{и} \quad D \to \ldots \to E. \]

3. Ищем кратчайший путь от \(A\) до \(D\):

• \(A \to D = 6\);
• \(A \to B \to D = 5+4=9\);
• \(A \to C \to D = 9+2=11\).

Минимум — \(6\).

4. Ищем кратчайший путь от \(D\) до \(E\):

• \(D \to E = 5\);
• \(D \to C \to E = 2+2=4\);
• \(D \to A \to E = 6+9=15\).

Минимум — \(4\).

5. Складываем:

\[ 6+4=10. \]

Получается путь

\[ A \to D \to C \to E \]

длиной

\[ 6+2+2=10. \]

Для проверки: путь \(A \to D \to E\) даёт \(6+5=11\), а \(A \to B \to D \to C \to E\) — \(5+4+2+2=13\). Оба длиннее.

Ответ: 10.