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

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

2. Переберём допустимые маршруты.
Начинаем в исходном пункте и по очереди выбираем каждую существующую дорогу в ещё не посещённый пункт. Продолжаем до конечного пункта; если дальше двигаться нельзя, возвращаемся к последнему выбору. Так рассматриваем все простые пути, а не только маршруты с наименьшим числом дорог. Из полученных путей оставляем только проходящие через E. Для каждого оставшегося пути складываем длины его дорог:
A—B—E—C—F—D: 5 + 2 + 5 + 4 + 5 = 21 ед. длины.
A—B—E—D: 5 + 2 + 3 = 10 ед. длины.
A—C—E—B—D: 3 + 5 + 2 + 6 = 16 ед. длины.
A—C—E—D: 3 + 5 + 3 = 11 ед. длины.

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

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

Ответ: 10.