ГДЗ 4. Между населенными пунктами A, B, C, D построены дороги, протяженность которых (в километрах) приведена в табли...
4. Между населенными пунктами 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 и вычислим их длину:
- Прямой путь:
- $\text{A} - \text{C} = 7$
- Пути через одну промежуточную вершину:
- $\text{A} - \text{B} - \text{C} = 2 + 5 = 7$
- $\text{A} - \text{D} - \text{C} = 4 + 2 = 6$
- Пути через две промежуточные вершины:
- $\text{A} - \text{B} - \text{D} - \text{C} = 2 + 1 + 2 = 5$
- $\text{A} - \text{D} - \text{B} - \text{C} = 4 + 1 + 5 = 10$
Сравнивая длины всех маршрутов ($7$, $7$, $6$, $5$, $10$), получаем, что кратчайшим является путь $\text{A} - \text{B} - \text{D} - \text{C}$ длиной $5$.
Ответ: 5