Кратчайший путь в графе
Между остановками ходят разные автобусы. Расстояние, которое проезжает каждый автобус, приведено в таблице. Найди кратчайшее расстояние между остановками А и Д.
| А | Б | В | Г | Д | |
|---|---|---|---|---|---|
| А | 1 | 3 | |||
| Б | 1 | 2 | 6 | ||
| В | 3 | 3 | |||
| Г | 2 | 3 | 3 | ||
| Д | 6 | 3 |
Решение
Из таблицы получаем дороги: А–Б =
Прямой дороги от А до Д нет, перебираем маршруты:
- А–Б–Д:
- А–Б–Г–Д:
- А–В–Г–Д:
Наименьшее значение получается у маршрута А–Б–Г–Д.
Ответ
✓ dzmen.ru
Помогло?
