Карточки
Тесты
Главная
Курсы
4. Работа с таблицами: #292793
Между населёнными пунктами $A$, $B$, $C$, $D$, $E$ построены дороги, протяжённость которых приведена в таблице.
| $A$ | $B$ | $C$ | $D$ | $E$ | |
|---|---|---|---|---|---|
| $A$ | $3$ | $9$ | $8$ | $9$ | |
| $B$ | $3$ | $4$ | |||
| $C$ | $9$ | $3$ | $2$ | ||
| $D$ | $8$ | $4$ | $3$ | $2$ | |
| $E$ | $9$ | $2$ | $2$ |
Определите длину кратчайшего пути между пунктами $A$ и $E$, проходящего через пункт $D$. Передвигаться можно только по дорогам, указанным в таблице. Каждый пункт можно посетить только один раз.
Рассмотрим возможные пути из пункта $A$ в пункт $E$, проходящие через пункт $D$.
- Путь $A\to D\to E$ имеет длину: $8+2=10$.
- Путь $A\to B\to D\to E$ имеет длину: $3+4+2=9$.
- Путь $A\to C\to D\to E$ имеет длину: $9+3+2=14$.
- Путь $A\to D\to C\to E$ имеет длину: $8+3+2=13$.
- Путь $A\to B\to D\to C\to E$ имеет длину: $3+4+3+2=12$.
Наименьшую длину имеет путь $A\to B\to D\to E$.
Длина кратчайшего пути: $9$.
20
