Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и F,
Реши задание на изображении
Сверь числа и знаки с фото.
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых (в километрах) приведена в таблице.
A B C D E F A 3 5 15 B 3 1 4 C 5 1 2 9 D 4 2 3 6 E 3 4 F 15 9 6 4 Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт C. Передвигаться можно только по дорогам, указанным в таблице. Ответ: ________________________________________.
Ответ: 12 км. Кратчайший маршрут: \[ A\to B\to C\to D\to F. \]
Как понять
Таблица симметрична, значит дороги двусторонние: например, \(AB=BA=3\).
Путь \(A\to F\), проходящий через \(C\), делим на две части: \(A\to C\) и \(C\to F\). Каждую часть можно минимизировать отдельно.
Кратчайший путь \(A\to C\):
- \(A\to C=5\);
- \(A\to B\to C=3+1=4\) — короче.
Значит \(d(A,C)=4\).
Кратчайший путь \(C\to F\):
- \(C\to F=9\);
- \(C\to D\to F=2+6=8\);
- \(C\to D\to E\to F=2+3+4=9\).
Значит \(d(C,F)=8\).
Итого: \[ 4+8=12. \]
Проверка: по таблице \(AB=3\), \(BC=1\), \(CD=2\), \(DF=6\), поэтому \[ 3+1+2+6=12. \] Путь действительно проходит через \(C\), и более короткого пути с этим условием нет.
