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