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

•  TDictionary Custom Sort  1 182

•  Fast Watermark Sources  1 459

•  3D Designer  2 347

•  Sik Screen Capture  1 877

•  Patch Maker  2 017

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

•  ListBox Drag & Drop  1 512

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

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

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

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

•  Canvas Drawing  1 259

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

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

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

•  Paint on Shape  706

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

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

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

•  Пазл Numbrix  796

 

 

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

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

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

 

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

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

Просмотры: 539
Дата: 30.06.2021, Автор: Gary Darby
Скачивания: 3
Написать сообщение:

 

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


 

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


Поисковик

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

Поиск файлов

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

 

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

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

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

 

© 2004-2022 "DS"

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