Недавно добавленные исходники

•  3D Designer  433

•  Sik Screen Capture  309

•  Patch Maker  269

•  Айболит (remote control)  341

•  ListBox Drag & Drop  247

•  Доска для игры Реверси  4 732

•  Графические эффекты  297

•  Рисование по маске  229

•  Перетаскивание изображений  249

•  Canvas Drawing  265

•  Рисование Луны  252

•  Поворот изображения  145

•  Рисование стержней  144

•  Paint on Shape  109

•  Генератор кроссвордов  148

•  Головоломка Paletto  142

•  Теорема Монжа об окружностях  175

•  Пазл Numbrix  102

•  Заборы и коммивояжеры  183

•  Игра HIP  123

 

 

Архив исходников

   
  Базы данных
  Графика & Мультимедиа
  Сети & Интернет
  Система
  Разное
   

Ссылки и Баннеры ...

 

Delphi Sources

Delphi Sources

 




 

ИСХОДНИК ПРОГРАММЫ

 

. : Дейкстра: поиск кратчайшего пути : .

 

Delphi - Алгоритм для нахождения кратчайшего пути от исходного узла до всех смежных узлов

Исходник программы, показывающей пример нахождения кратчайшего расстояния от исходного узла до всех смежных узлов. Это еще одна реализация алгоритма Дейкстры поиска по графу кратчайшего пути. Таким образом, на каждой фазе работы алгоритма к каждому узлу сохраняется только один путь.

Модуль имеет процедуры поиска «в глубину» и «в ширину», которые ищут пути перехода от некоторого начального узла к некоторому целевому узлу. Недавно я изменил структуру, чтобы можно было связать веса с ребрами, соединяющими узлы. Новая процедура реализует алгоритм поиска кратчайшего пути Дейкстры, умный и относительно эффективный способ поиска кратчайших путей между узлами. Алгоритм находит кратчайшие пути от указанного начального узла к любому другому достижимому узлу (или ко всем достижимым узлам) для графов с положительными весами (расстояниями) между узлами.

Псевдокод:

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

Демонстрационная программа случайным образом присваивает веса графу и вызывает процедуру поиска Дейкстры, чтобы найти кратчайший путь. Функция «подробного описания» позволит шаг за шагом увидеть работу алгоритма.

Просмотры: 84
Дата: 30.06.2021, Автор: Gary Darby
Написать сообщение:
 

 

Скачать (325 Кб)   ↓ 0   Регистрация >>


 

Похожие исходники


Поисковик

Поиск символа

Поиск файлов

Поиск открытых файлов

 

Findup (поиск дублей)

A Star (нахождение кратчайшего пути)

Нахождение кратчайшего пути

 

© 2004-2021 "DS"

Соглашение пользователя / Реклама / Карта сайта             Created by BrokenByte Software