Цель работы — найти максимальный поток в ориентированной транспортной сети и сравнить два способа выбора увеличивающего пути.
Файл 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.
