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

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

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

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

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

Ответ: 11.