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