Задание EGEINF5AEA27: Графы, таблицы и маршруты

Решение.
Длина маршрута равна сумме длин его дорог. Отсутствие числа означает отсутствие прямого соединения, а не дорогу нулевой длины. Все длины положительны, поэтому обход с возвращением в уже посещённый пункт только увеличивает путь.
Найдём кратчайшие расстояния от A до всех пунктов. Обозначим их текущие оценки через d. В начале d(A) = 0, а остальные оценки равны ∞: маршрут пока не найден.
Каждый раз выбираем ещё не обработанный пункт с наименьшей оценкой. Его расстояние уже окончательно: любая дорога через более далёкий пункт не даст меньшую длину. Для соседа Y пункта X сравниваем прежнее d(Y) с d(X) + длина дороги XY и оставляем меньшее.
Обрабатываем A: d(A)=0, d(B)=4, d(C)=8, d(D)=4, d(E)=∞, d(F)=∞, d(G)=18.
Обрабатываем B: d(A)=0, d(B)=4, d(C)=8, d(D)=4, d(E)=∞, d(F)=∞, d(G)=18.
Обрабатываем D: d(A)=0, d(B)=4, d(C)=7, d(D)=4, d(E)=∞, d(F)=∞, d(G)=18.
Обрабатываем C: d(A)=0, d(B)=4, d(C)=7, d(D)=4, d(E)=10, d(F)=∞, d(G)=18.
Обрабатываем E: d(A)=0, d(B)=4, d(C)=7, d(D)=4, d(E)=10, d(F)=14, d(G)=17.
Обрабатываем F: d(A)=0, d(B)=4, d(C)=7, d(D)=4, d(E)=10, d(F)=14, d(G)=16.
Обрабатываем G: d(A)=0, d(B)=4, d(C)=7, d(D)=4, d(E)=10, d(F)=14, d(G)=16.
Минимальная длина от A до G равна 16. Она достигается маршрутом A → D → C → E → F → G: 4 + 3 + 3 + 4 + 2 = 16.
Проверка нижней оценки: для каждой разрешённой дороги X–Y итоговые значения удовлетворяют d(Y) ≤ d(X) + длина XY в обоих направлениях. Складывая эти неравенства вдоль любого пути от начала, получаем, что его длина не меньше d(G). Показанный маршрут достигает этой оценки, значит, он действительно кратчайший.
Варианты ответа: 1) 15, 2) 16, 3) 17, 4) 18. Число 16 стоит под номером 2. В ответ записываем номер варианта.
Ответ: 2.