Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Бурков В.Н. Элементы теории графов
 
djvu / html
 

Алгоритм 2 (алгоритм Форда).
Шаг 0: Помечаем нулевую вершину индексом Я0 = 0, все ос-
тальные вершины индексами Я° = +<х> i = \,п ;
Т Т Таг k: Рассматриваем все дуги. Если для дуги (г; у),
Я*"1-Я*"1 >1у, то вычисляем новое значение Я* = Я*"1 + 1у.
Индексы устанавливаются за конечное число шагов. Обозна-
чим { Яг- } - установившиеся значения индексов, которые обладают
Л*
следующим свойством: величина Яг- равна длине кратчайшего
пути из нулевой вершины в вершину г. Кратчайший путь из вер-
шины 0 в вершину г определяется методом обратного хода.
Если длины всех дуг неотрицательны, то для поиска кратчай-
шего пути применим следующий алгоритм.
Алгоритм 3.
Шаг 0: Помечаем нулевую вершину индексом Я0 = 0;
Т Т Таг k: Пусть уже помечено некоторое множество вершин.
Обозначим Q - множество непомеченных вершин, смежных с
помеченными. Для каждой вершины k e Q вычисляем величину
§t = min (Яг- + lit), где минимум берется по всем помеченным вер-
шинам z, смежным с вершиной k. Помечаем вершину k, для кото-
рой величина ^ минимальна, индексом Я* = §t.
Подобную процедуру повторяем до тех пор, пока не будет по-
мечена вершина п. Длина кратчайшего пути равна Я„, а сам крат-
чайший путь определяется так, как это было описано выше.
Запишем задачу о кратчайшем пути как задачу линейного про-
граммирования (ЛП). Пусть ху = 1, если дуга (z;y) входит в путь1 \л,
Ху = 0, если дуга (z;y) не входит в путь /л, i,j = 0,п .
Задачу о минимальном пути можно записать в виде :
(1)Ддс)=
1 Будем считать, что имеются две дуги между каждой парой вершин, так как,
если их нет в исходном графе, то, положив их длину равной бесконечности, мы
заведомо исключим их из решения.
2 Ограничение (2) отражает требование того, что в искомом пути из входа
выходит одна дуга и в выход заходит одна дуга. Ограничение (3) обеспечивает
равенство числа заходящих и выходящих в любую промежуточную вершину дуг.
9

 

1 2 3 4 5 6 7 8 9 10 20


Математика