Сравнение алгоритмов Расст-Рек и Дейкстры

Реализация

Мы надеемся, что функцию поиска меньшего из двух целых чисел min, использованную в тексте программы, читатели смогут написать самостоятельно.

dist[s]:= 0; done[s]:= true; last:= s;for i:= 1 to N-1 do begin for x:= 1 to N do if (sm[last,x]<>0)and(not done[x]) then dist[x]:= min(dist[x],dist[last]+ sm[last,x]); min_dist:= MaxLongInt; for x:= 1 to N do if (not done[x])and(min_dist>dist[x]) then begin min_dist:= dist[x]; last:= x; end; done[last]:= true; end.

Сложность рекурсивного алгоритма пропорциональна N!, а алгоритм Дейкстры имеет сложность ~N2. Комментарии, как говорится, излишни.

1) См. лекцию 11.
2) См. лекцию 9.
3) Точнее, результатом печати значений, содержащихся в вершинах ДСА.
4) Вместо простой пометки вершины здесь можно производить выполнение любой осмысленной функции.
5) См. лекцию 9.
6) См. предыдущую лекцию.
7) Dijkstra E.W. A Note on Two Problems in Connection with Graphs, 1959.

 

13. Лекция: Модульная структура программы:
Методы работы с модулями. Стандартные модули языка Pascal. Создание модульных программ. Передача в программу аргументов из командной строки.