Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Catalog · How the catalog works

Random project

Dijkstra-OOP

View on GitHub

Member rating

No ratings yet.

Sign in to rate this project.

README

Dijkstra — Free Pascal

Реализация алгоритма Дейкстры на Free Pascal 3.2.2 с использованием объектно-ориентированного подхода.

Проект разбит на отдельные модули и не использует явные указатели (^, New, Dispose).

Возможности

  • поиск кратчайших путей алгоритмом Дейкстры;
  • восстановление маршрута между вершинами;
  • ориентированные и неориентированные рёбра;
  • проверка корректности вершин и весов;
  • минимальная приоритетная очередь на основе бинарной кучи;
  • разделение графа, очереди и алгоритма по отдельным модулям.

Структура проекта

text
.
├── main.pas
├── Graph.pas
├── Dijkstra.pas
├── PriorityQueue.pas
└── .gitignore

Graph.pas

Содержит классы:

  • TEdge — ребро графа;
  • TGraph — граф и управление его рёбрами.

PriorityQueue.pas

Содержит минимальную приоритетную очередь:

  • TPriorityQueue
  • TQueueItem

Очередь реализована на основе бинарной min-heap.

Dijkstra.pas

Содержит класс:

pascal
TDijkstra

Отвечает за:

  • запуск алгоритма;
  • вычисление расстояний;
  • хранение предыдущих вершин;
  • восстановление кратчайшего пути.

main.pas

Точка входа приложения и пример использования алгоритма.

Требования

  • Free Pascal Compiler 3.2.2
  • Linux / Windows / macOS
  • JetBrains IDE с поддержкой Pascal через Pascal Flow — опционально

Сборка

Выполнить в корне проекта:

bash
fpc main.pas

После успешной компиляции будет создан исполняемый файл:

text
Main

Запуск:

bash
./Main

Пример результата

text
Distance: 8
Path: 0 -> 1 -> 3 -> 4 -> 5

Принцип работы

Алгоритм Дейкстры начинает поиск из исходной вершины и постепенно выбирает вершину с минимальным известным расстоянием.

Для каждой соседней вершины выполняется релаксация:

text
newDistance = currentDistance + edgeWeight

Если новое расстояние меньше известного, оно обновляется, а вершина добавляется в приоритетную очередь.

Алгоритм работает с рёбрами, веса которых неотрицательны.

Особенности реализации

Проект использует классы Pascal вместо явных указателей:

pascal
TEdge = class

Это позволяет работать с объектными ссылками без ручного использования:

pascal
^
New
Dispose

При этом объекты графа явно освобождаются владельцем в Destroy.

Лицензия

Учебный проект. Используйте код свободно для обучения и экспериментов.