Graph-Pathfinding-Experiments

Сравнительное исследование производительности алгоритмов поиска кратчайшего пути в графах: Dijkstra, A*, BFS и GBFS.
Эксперименты проводились на двух типах тестовых графов:

1. Решётки (grid) с единичными весами рёбер.
2. Случайные (random) графы, где вес рёбер может принимать значения в диапазоне от 1 до 10.

Содержимое репозитория

• algorithms.py
  Содержит реализации алгоритмов Dijkstra, A*, BFS (невзвешенный вариант) и GBFS, а также набор эвристических функций (евклидова и манхэттенская).

• generate_graphs.py
  Генерация тестовых графов двух типов:

  • Случайный граф (random) с вероятностью ребра p и весами от 1 до 10.
  • Решётчатый граф (grid) заданных размеров (например, 50×50, 100×100).

• run_experiments.py
  Основной скрипт для запуска экспериментов:

  1. Генерирует или загружает тестовые графы.
  2. Запускает каждый алгоритм заданное число раз.
  3. Замеряет время выполнения, потребление памяти и длину найденного пути.
  4. Сохраняет результаты в CSV или Markdown-таблицы.

• plot_results.py
  Считывает итоги экспериментов (CSV/MD) и строит графики (время, память, отклонение пути).
  Использует matplotlib для визуализации.

Требования

• Python 3.10 (или выше).
• Библиотеки:
  • psutil (замер потребления памяти).
  • matplotlib (построение графиков).
  • csv и стандартные модули Python (heapq, argparse, time и т. д.).

Пример установки необходимых зависимостей:

pip install psutil matplotlib