Кратчайший путь между пунктами по таблице расстояний

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

1. 1

   Шаг 1. Переводим таблицу в список дорог

   	А	Б	В	Г	Д	Е
   А	—	4	2	0	0	0
   Б	4	—	1	5	0	0
   В	2	1	—	7	9	0
   Г	0	5	7	—	2	9
   Д	0	0	9	2	—	3
   Е	0	0	0	9	3	—

   Берём клетки выше диагонали: А–Б 4, А–В 2, Б–В 1, Б–Г 5, В–Г 7, В–Д 9, Г–Д 2, Г–Е 9, Д–Е 3. Девять дорог, все двусторонние.

2. 2

   Шаг 2. Заводим метки расстояний

   Для каждого пункта храним метку $d(X)$ — лучшую известную длину пути из А в $X$. В начале $d(А)=0$, остальные считаем «бесконечными».

   Работаем так: выбираем пункт с наименьшей меткой, который ещё не обработан, и через него пытаемся улучшить метки его соседей. Первый шаг: соседи А — это Б и В, поэтому $d(Б) \le 4$ и $d(В) \le 2$.