Исходник программы, показывающей пример нахождения кратчайшего расстояния от исходного узла до всех смежных узлов. Это еще одна реализация
алгоритма Дейкстры поиска по графу кратчайшего пути. Таким образом, на каждой фазе работы алгоритма к каждому узлу сохраняется только один путь.
Модуль имеет процедуры поиска «в глубину» и «в ширину», которые ищут пути перехода от некоторого начального узла к некоторому целевому узлу. Недавно я изменил структуру, чтобы можно было связать веса с ребрами, соединяющими узлы. Новая процедура реализует алгоритм поиска кратчайшего пути Дейкстры, умный и относительно эффективный способ поиска кратчайших путей между узлами. Алгоритм находит кратчайшие пути от указанного начального узла к любому другому достижимому узлу (или ко всем достижимым узлам) для графов с положительными весами (расстояниями) между узлами.
Псевдокод:
for all vertices v,
dist(v) = infinity;
dist(first) = 0;
endfor
place all vertices in set toBeChecked;
while toBeChecked is not empty,
select v: min(dist(v)) in toBeChecked;
remove v from toBeChecked;
for u in toBeChecked, and path from v to u exists
{i.e. for unchecked adjacents to v}
do
if dist(u) > dist(v) + weight({u,v}),
then
dist(u) = dist(v) + weight({u,v});
set predecessor of u to v
save minimum distance to u in array "d"
endif
enddo
endwhile
Демонстрационная программа случайным образом присваивает веса графу и вызывает процедуру поиска Дейкстры, чтобы найти кратчайший путь. Функция «подробного описания» позволит шаг за шагом увидеть работу алгоритма.
Базы данных
