Задача о кратчайшем пути между двумя пунктами

Известна схема дорог. Требуется перевезти груз из одного пункта в другой по маршруту минимальной длины.

Двигаясь от конечного пункта к начальному пункту, каждой вершине припишем число по определенным правилам. Конечной вершине присвоим число 0. Если i-я вершина в направлении от начального пункта к конечному пункту непосредственно соединена с вершинами j₁,…, j_k, которым приписаны числа r(j₁),…, r(j_k), то вершине i приписывается число r(i) = (r(j_s) + t(i, j_s)), где t(i, j_s) – длина ребра (i, j_s).

Пусть этот минимум достигается для вершины j_m. Тогда ребро (i, j_m) покажем двумя чертами со стрелкой от i к j_m. Если таких j_m несколько, то на этом шаге будет несколько двойных ребер.

Число, приписанное начальному пункту, равно минимальной длине искомого маршрута. Двигаться от начального пункта к конечному пункту нужно по двойным ребрам со стрелками.

Пример 3. Найдем маршрут минимальной длины от пункта 1 к пункту 11.