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