Кратчайший путь в графе
Найдите кратчайший путь из A в C. Длины рёбер: AB = 3, AD = 5, AC = 9, BC = 6, DC = 3, DE = 1, EC = 1.
Решение
Перебираем все пути из A в C:
- A–C:
. - A–B–C:
. - A–D–C:
. - A–D–E–C:
.
Наименьшая длина у пути A–D–E–C.
💡 Почему так
Длина пути — сумма длин его рёбер. Кратчайший путь не всегда содержит наименьшее число рёбер: прямое ребро AC (
Ответ
✓ dzmen.ru
Помогло?
