Задание OGEINF556B44: Кратчайший путь по таблице дорог

1. Прочитаем таблицу дорог.
Нужно пройти из A в C. Число на пересечении строки и столбца — длина прямой дороги между соответствующими пунктами. Пустая клетка означает, что такой дороги нет; считать её дорогой нулевой длины нельзя. Таблица симметрична, поэтому каждую дорогу записываем один раз:
A—B: 4; A—E: 1; B—D: 1; B—E: 2; C—D: 4; D—E: 4.
Все длины измеряются в километрах. Каждый пункт разрешено посетить только один раз.

2. Переберём допустимые маршруты.
Начинаем в исходном пункте и по очереди выбираем каждую существующую дорогу в ещё не посещённый пункт. Продолжаем до конечного пункта; если дальше двигаться нельзя, возвращаемся к последнему выбору. Так рассматриваем все простые пути, а не только маршруты с наименьшим числом дорог. Для каждого оставшегося пути складываем длины его дорог:
A—B—D—C: 4 + 1 + 4 = 9 км.
A—B—E—D—C: 4 + 2 + 4 + 4 = 14 км.
A—E—B—D—C: 1 + 2 + 1 + 4 = 8 км.
A—E—D—C: 1 + 4 + 4 = 9 км.

3. Сравним длины.
Проверены все допустимые пути из A в C; их количество — 4. Полученные длины: 9, 14, 8, 9. Наименьшая из них равна 8 км. Она достигается на маршруте A—E—B—D—C. Ни один путь не пропущен: на каждом шаге рассмотрены все соседние ещё не посещённые пункты, а ограничения условия проверены до сравнения длин.

4. Проверка.
Проверим один кратчайший маршрут по исходной таблице: A—E = 1, E—B = 2, B—D = 1, D—C = 4.
Сумма длин: 1 + 2 + 1 + 4 = 8 км. Начало маршрута — A, конец — C; все дороги существуют, все пункты в маршруте различны. В ответ требуется длина пути, поэтому записываем только число.

Ответ: 8.