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

Алгоритм для сетей без циклов

Обозначим:  – расстояние на сети между смежными узлами;  – кратчайшее расстояние между узлами  и . Считаем, что кратчайшее расстояние до первого узла сети равно нулю, . При построении используется идея рекурсивных вычислений. Для того чтобы найти кратчайшее расстояние до некоторого узла, необходимо найти кратчайшие расстояния до узлов непосредственно предшествующих этому узлу. Поэтому можно записать:

,                                                (9.1)

где  – кратчайшее расстояние до предыдущего узла, непосредственно предшествующего узлу ;  – расстояние между текущим узлом  и предыдущим узлом .

Отсюда получаем, что кратчайшее расстояние  до узла  можно вычислить лишь после того, как определено кратчайшее расстояние до каждого предыдущего узла , соединенного дугой с узлом .

Процедура построения кратчайшего пути завершается, когда будет найдено , где n число узлов в сети.

Пример 9.2

Найти кратчайший путь из вершины 1 в вершину 7 для сети (рис. 10.11).

Решение. Полагаем . Узлам 2 и 3 непосредственно предшествует только узел 1, следовательно,

, .

Далее в соответствии с общей формулой (9.1), последовательно находим (в скобках указаны вершины, которые соответствуют кратчайшему пути, для того чтобы можно было восстановить этот путь):

 (из 1);

 (из 2);

 (из 3);

 (из 5).

Таким образом, маршрут минимальной длины (на рис. 10.11 выделен жирными дугами): . Протяженность этого маршрута равна 13.