Skip to content

Latest commit

 

History

History
53 lines (33 loc) · 2.75 KB

README.md

File metadata and controls

53 lines (33 loc) · 2.75 KB

Лабораторная работа №4 — максимальный поток

Цель работы — найти максимальный поток в ориентированной транспортной сети и сравнить два способа выбора увеличивающего пути.

Реализованные алгоритмы

Форд—Фалкерсон с поиском в глубину

Файл Lab4 классический вариант.py ищет увеличивающий путь с помощью DFS. Оценка сложности для целочисленных пропускных способностей — O(E · |F|), где E — число рёбер, а |F| — величина максимального потока.

Эдмондс—Карп

Файл Lab4 с поиском в ширину.py выбирает кратчайший по количеству рёбер увеличивающий путь с помощью BFS. Оценка сложности — O(V · E²).

Обе реализации:

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

Исходная сеть

Ориентированный граф с пропускными способностями

В исходниках приведено несколько тестовых наборов рёбер с известными ответами: 90, 60 и 10.

Запуск

python -m venv .venv

# Windows PowerShell
.venv\Scripts\Activate.ps1

pip install networkx matplotlib

python "Lab4 классический вариант.py"
python "Lab4 с поиском в ширину.py"

Запускайте программы из каталога Lab4. Вариант с BFS сохраняет визуализацию в файл Граф.png; классический вариант показывает её в окне Matplotlib.

Чтобы исследовать другой пример, выберите нужный список edges в функции main и укажите соответствующие вершины истока и стока.

Технологии

  • Python;
  • NetworkX;
  • Matplotlib;
  • collections.deque для поиска в ширину;
  • стандартные модули copy и typing.