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

Реализация

Мы надеемся, что функцию поиска меньшего из двух целых чисел 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!, а алгоритм Дейкстры имеет сложность ~N². Комментарии, как говорится, излишни.

¹⁾ См. лекцию 11.
²⁾ См. лекцию 9.
³⁾ Точнее, результатом печати значений, содержащихся в вершинах ДСА.
⁴⁾ Вместо простой пометки вершины здесь можно производить выполнение любой осмысленной функции.
⁵⁾ См. лекцию 9.
⁶⁾ См. предыдущую лекцию.
⁷⁾ Dijkstra E.W. A Note on Two Problems in Connection with Graphs, 1959.

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

Дата добавления: 2014-01-03