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