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


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

Обозначим ly - длину дуги (i;j). Кратчайший путь в сети,
имеющей правильную нумерацию, определяется следующим
алгоритмом.
Алгоритм 1.
Шаг 0: Помечаем нулевую вершину индексом Я0 = 0;
Т Т Таг k: помечаем вершину k индексом Я* = min (Яг + /а).
i Индекс выхода Я„ будет равен длине кратчайшего пути1. На
рисунке 2 приведен пример применения алгоритма 1 для опреде-
ления кратчайшего пути (числа у дуг равны длинам дуг, индексы
вершин помещены в квадратные скобки, кратчайший путь выделен
двойными линиями).
Когда индексы (называемые в некоторых задачах потенциа-
лами вершин) установятся, кратчайший путь определяется методом
обратного хода от выхода к входу, то есть кратчайшим является
путь ju = (0; if, i2;...; /„./; и), такой, что 1^п = Я„- Я„.; и т.д.
Рис. 2. Поиск кратчайшего пути
Следующий алгоритм дает возможность определять кратчай-
ший путь в общем случае (то есть при произвольной нумерации
вершин).
' Алгоритм 1 для задач динамического программирования отражает принцип
оптимальности Беллмана: если ищется кратчайший путь между двумя точка-
ми, то длина пути между любыми двумя точками кратчайшего пути также
должна быть минимальна.

 

1 2 3 4 5 6 7 8 9 10 20


Математика