Поиск кратчайшего и длиннейшего пути в графе
По схеме дорог определите длину путей от пункта А до пункта Б.
Самый короткий путь: [ ] км
Самый длинный путь: [ ] км
Решение
Рассмотрим все возможные простые пути (без повторного посещения вершин) от пункта А до пункта Б:
Из пункта А ведут стрелки:
: длина км : длина км : длина км
Из пункта В можно пойти только в Г:
: км.
Из пункта Д можно пойти только в Г:
: км.
Таким образом, пути до вершины Г:
: км : км : км
Из пункта Г пути ведут в Б, Е, Ж:
- Напрямую в Б:
: км
- Через Е:
: км
- Через Ж:
: км
Составим все возможные пути от А до Б:
- Через
( км): : км : км : км
- Через
( км): : км : км : км
- Через
( км): : км : км : км
Сравнивая длины:
- Самый короткий путь равен
км ( ). - Самый длинный простой путь равен
км ( ).
Ответ
Самый короткий путь:
Самый длинный путь:
Помогло?
