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