| A | Б | B | Г | Д | E | |
|---|---|---|---|---|---|---|
| A | 3 | 4 | 16 | |||
| Б | 3 | 3 | 4 | |||
| B | 4 | 3 | 1 | 6 | ||
| Г | 4 | 1 | 2 | 6 | ||
| Д | 2 | 1 | ||||
| E | 16 | 6 | 6 | 1 |
Чтобы найти кратчайший путь из А в Е через Г, нужно рассмотреть все возможные варианты маршрута, проходящие через Г, и выбрать самый короткий.
Возможные маршруты:
Рассчитаем длину каждого маршрута:
A → Г → E
Из таблицы видно, что прямого пути из А в Г нет, следовательно, этот вариант не подходит.
A → Б → Г → E
Длина пути A → Б = 3 км
Длина пути Б → Г = 4 км
Длина пути Г → E = 6 км
Общая длина пути A → Б → Г → E = 3 + 4 + 6 = 13 км
A → B → Г → E
Длина пути A → B = 4 км
Длина пути B → Г = 1 км
Длина пути Г → E = 6 км
Общая длина пути A → B → Г → E = 4 + 1 + 6 = 11 км
Сравним длины маршрутов:
Кратчайший путь из А в Е через Г: A → B → Г → E длиной 11 км.
Ответ: 11