Найдите кратчайший путь из пункта A в пункт F.
Ответ
Выпишем дороги: AB = 2, AC = 4, BC = 1, BE = 7, CD = 3, CE = 4, DE = 3, EF = 2. В пункт F ведёт единственная дорога — из E, поэтому нужно найти кратчайший путь из A в E и добавить 2 км.
Перебираем пути из A в E без повторения пунктов:
- A–B–E: \( 2 + 7 = 9 \);
- A–B–C–E: \( 2 + 1 + 4 = 7 \);
- A–B–C–D–E: \( 2 + 1 + 3 + 3 = 9 \);
- A–C–E: \( 4 + 4 = 8 \);
- A–C–D–E: \( 4 + 3 + 3 = 10 \);
- A–C–B–E: \( 4 + 1 + 7 = 12 \).
Кратчайший путь до E — A–B–C–E длиной 7 км, до F — ещё 2 км.
Ответ: A–B–C–E–F, длина пути 9 км.