Экстремальные пути и контуры на графах

Задача о кратчайшем пути. Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске

кратчайшего пути (пути минимальной длины) от входа до выхода сети.

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

Предположим, что в сети нет контуров. Тогда всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место j > i. Такая нумерация называется правильной. Легко показать, что в сети без контуров всегда существует правильная нумерация.

Обозначим – длину дуги (i; j). Следующий алгоритм дает возможность определять кратчайший путь в общем случае (то есть при произвольной нумерации вершин).

Aлгоритм Форда.

Шаг 0: Помечаем нулевую вершину индексом , все остальные вершины индексами ;

Шаг k: Рассматриваем все дуги. Если для дуги (i; j), , то вычисляем новое значение

Индексы устанавливаются за конечное число шагов. Обозначим установившиеся значения индексов, которые обладают

следующим свойством: величина равна длине кратчайшегопути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.