Как найти кратчайший путь между городами по схеме дорог

Решение по шагам

1. 1

   Шаг 1. Чем короткий путь отличается от пути с малым числом дорог

   «Кратчайший» — это путь с наименьшей суммарной длиной, а не с наименьшим количеством дорог. Например, маршрут А–В–Д состоит всего из двух дорог, но его длина $5+9=14$ км — как мы увидим, это далеко не лучший вариант.

   Дороги двусторонние, значит по каждой можно ехать в любую сторону.

2. 2

   Шаг 2. Метод меток: расставляем расстояния от А

   Заведём для каждого посёлка метку $d(X)$ — найденную на данный момент кратчайшую длину пути из А в $X$. Начинаем с $d(А)=0$.

   Прямые дороги из А дают первые метки:

   $d(Б) = 3$ км, $d(В) = 5$ км.

   Дальше метки будем уточнять: если через какой-то посёлок доехать дешевле, метка уменьшается.