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