Johnson Algorithm GUI

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

Описание

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

Возможности

• Ввод матрицы смежности через текстовое поле или загрузку из файла
• Выполнение алгоритма Джонсона для поиска кратчайших путей
• Визуализация графа с помощью Graphviz
• Отображение результатов в удобном табличном формате
• Сохранение и загрузка матриц смежности
• Предустановленные примеры графов

Требования

• Python 3.12 или выше
• Graphviz (для визуализации графов)
• Зависимости Python (устанавливаются автоматически):
  • graphviz>=0.20.0
  • pillow>=10.0.0

Установка

1. Клонируйте репозиторий или скачайте проект

2. Установите зависимости:

   pip install -r requirements.txt

   или используйте uv:

   uv sync

3. Установите Graphviz:

   • Windows: Скачайте установщик с официального сайта
   • Linux: sudo apt-get install graphviz (Ubuntu/Debian) или sudo yum install graphviz (CentOS/RHEL)
   • macOS: brew install graphviz

   Примечание: В проекте уже включена версия Graphviz для Windows в папке Graphviz-14.1.1-win64/, которая будет использоваться автоматически.

Использование

Запустите приложение:

python main.py

Формат ввода матрицы смежности

Матрица должна быть квадратной, где:

• Числа разделены пробелами
• Строки разделены переносами строк
• inf или пустая строка означает отсутствие ребра
• 0 означает ребро с весом 0 (включая петли)
• Другие числа означают вес ребра

Пример:

0 1 3 inf
inf 0 1 2
inf inf 0 1
inf inf inf 0

Горячие клавиши

• Ctrl+O - Открыть файл
• Ctrl+S - Сохранить файл
• F5 - Запустить алгоритм

Алгоритм Джонсона

Алгоритм Джонсона состоит из трех этапов:

1. Создание расширенного графа: Добавление фиктивной вершины с нулевыми ребрами ко всем остальным вершинам
2. Применение Беллмана-Форда: Определение перевешивающих весов для устранения отрицательных весов
3. Применение Дейкстры: Поиск кратчайших путей от каждой вершины с использованием перевешенных весов

Временная сложность: O(V² log V + VE), где V - количество вершин, E - количество ребер.

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

JohnsonAlgorithmGUI/
├── main.py                  # GUI приложение
├── johnson_algorithm.py     # Реализация алгоритма Джонсона
├── pyproject.toml          # Конфигурация проекта
├── README.md               # Документация
└── Graphviz-14.1.1-win64/  # Локальная версия Graphviz (Windows)

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

• Обработка ошибок: Полная валидация входных данных и обработка исключений
• Визуализация: Автоматическое создание и отображение графов
• Управление ресурсами: Автоматическая очистка временных файлов
• Типизация: Использование type hints для улучшения читаемости кода

Ограничения

• Алгоритм не работает с графами, содержащими отрицательные циклы
• Визуализация требует установленного Graphviz
• Максимальный размер загружаемого файла: 10 МБ

Лицензия

Этот проект предоставляется "как есть" для образовательных целей.

Версия

0.1.0