Определение максимальных потоков в сети

@vik23 · Регистрация: 07.12.2010

Студворк — интернет-сервис помощи студентам

Дан файл с описанием карты локальной компьютерной сети. Каждая связь имеет вес – объем информации, который можно прокачать через данное соединение за еденицу времени.
Написать программу, которая рисует на экране заданную компьютерную сеть и определяет, с какой максимальной скоростью можно передавать между компьютерами с номерами Mи N (задаются пользователем).

Вот, например, дан граф: ссылка
Получается, что максимальная скорость
между 2 и 4 будет 4 (путь: 2-5-4)
между 0 и 7 будет 4 (путь: 0-1-4-7)

Весь день голову ломаю, никак не подберу алгоритм. Какой здесь нужно применять?

@SlavaSSU · 04.06.2015, 18:41

будем перебирать ответ от больших значений к меньшим. вот зафиксировали число X, и будем пытаться найти путь, все ребра которого не меньше чем X. если такой путь есть, то все хорошо, выводим ответ и выходим. если такого пути нет, то уменьшим X и опять попробуем и т.д. Путь будем искать поиском в ширину или глубину, который не ходит по ребрам дешевле веса X. Теперь заметим, что наибольшее X, такое что существует путь в к-ом мин ребро не меньше X, можно искать двоичным поиском.

@vik23 · 04.06.2015, 22:10 **[ТС]**

SlavaSSU, спасибо, получилось!

Сообщение от SlavaSSU

Теперь заметим, что наибольшее X, такое что существует путь в к-ом мин ребро не меньше X, можно искать двоичным поиском.

Вот это не понял.
Оптимизации ради можно брать только такие X, веса которые существуют. Заранее их получив, конечно же

@SlavaSSU · 04.06.2015, 22:15

vik23, ну так различных весов столько, сколько и ребер. Т.е. надо будет КОЛВО РЕБЕР раз запускать поиск. А в случае с бинпоиском надо будет сделать всего около 30 поисков в ширину(глубину), если макс вес на ребрах ограничен миллиардом.

@Shamil1 · 04.06.2015, 22:36

Так можно веса всех рёбер записать в отсортированный массив (отбрасывая повторы) и искать нужный индекс двоичным поиском по этому массиву. Вместо log V_{max} будет $https://www.cyberforum.ru/cgi-bin/latex.cgi?log V_{count}$ .

@SlavaSSU · 04.06.2015, 22:45

Shamil1, что то же самое)

@Shamil1 · 05.06.2015, 02:20

SlavaSSU,
Если пропускные способности рёбер 1-100 и одно ребро 100000000 нам не придётся делать 30 поисков... хватит 7.

@wingblack · 05.06.2015, 07:43

Заменяем в теме "в сети" на "в графе" и ищем.
https://ru.wikipedia.org/wiki/Задача о максимальном потоке
http://algolist.manual.ru/maths/graphs/maxflows/

К слову, максимальный поток между двумя компьютерами может "ходить" по сети сразу несколькими путями, потому что по двум "трубам" "воды" прейдет больше чем по одной.

@SlavaSSU · 05.06.2015, 10:28

Shamil1, это я понимаю, я имею в виду что нет разницы, 10 или 60 поисков, но есть разница, 60 или КОЛВО РЕБЕР поисков.

@vik23 · 05.06.2015, 12:45 **[ТС]**

Сообщение от wingblack

К слову, максимальный поток между двумя компьютерами может "ходить" по сети сразу несколькими путями, потому что по двум "трубам" "воды" прейдет больше чем по одной.

А вот это интересное замечание
Как тогда решается задача? Находить непересекающиеся пути поиском в глубину и суммировать их минимальную пропускную способность?

Но проект уже готов, а сдавать его уже завтра. Оставлю так

@SlavaSSU · 05.06.2015, 13:09

vik23, тогда задача так и называется. Нахождение макс потока в сети. Но там просто так сам не придумаешь. Макс поток не обязательно ходит по неперсекающимся путям. Пути могут частично пересекаться.

во пример.
ищем поток от вершины 1 к вершине 6.

ребра (концы ребра и вес)

1 2 10
2 3 5
2 4 4
3 5 10
4 5 10
5 6 8

ОТвет: 8.

@wingblack · 05.06.2015, 16:45

Сообщение от vik23

Как тогда решается задача? Находить непересекающиеся пути поиском в глубину и суммировать их минимальную пропускную способность?

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

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	04.06.2015, 18:41
	Сообщение было отмечено vik23 как решение Решение будем перебирать ответ от больших значений к меньшим. вот зафиксировали число X, и будем пытаться найти путь, все ребра которого не меньше чем X. если такой путь есть, то все хорошо, выводим ответ и выходим. если такого пути нет, то уменьшим X и опять попробуем и т.д. Путь будем искать поиском в ширину или глубину, который не ходит по ребрам дешевле веса X. Теперь заметим, что наибольшее X, такое что существует путь в к-ом мин ребро не меньше X, можно искать двоичным поиском. 1

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	04.06.2015, 22:15
	vik23, ну так различных весов столько, сколько и ребер. Т.е. надо будет КОЛВО РЕБЕР раз запускать поиск. А в случае с бинпоиском надо будет сделать всего около 30 поисков в ширину(глубину), если макс вес на ребрах ограничен миллиардом. 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	04.06.2015, 22:36
	Так можно веса всех рёбер записать в отсортированный массив (отбрасывая повторы) и искать нужный индекс двоичным поиском по этому массиву. Вместо log V_{max} будет $https://www.cyberforum.ru/cgi-bin/latex.cgi?log V_{count}$ . 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	04.06.2015, 22:45
	Shamil1, что то же самое) 0

@Shamil1 Модератор 3136 / 2283 / 469 Регистрация: 26.03.2015 Сообщений: 8,886
	05.06.2015, 02:20
	SlavaSSU, Если пропускные способности рёбер 1-100 и одно ребро 100000000 нам не придётся делать 30 поисков... хватит 7. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	05.06.2015, 07:43
	Заменяем в теме "в сети" на "в графе" и ищем. https://ru.wikipedia.org/wiki/Задача о максимальном потоке http://algolist.manual.ru/maths/graphs/maxflows/ К слову, максимальный поток между двумя компьютерами может "ходить" по сети сразу несколькими путями, потому что по двум "трубам" "воды" прейдет больше чем по одной. 1

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	05.06.2015, 10:28
	Shamil1, это я понимаю, я имею в виду что нет разницы, 10 или 60 поисков, но есть разница, 60 или КОЛВО РЕБЕР поисков. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	05.06.2015, 13:09
	vik23, тогда задача так и называется. Нахождение макс потока в сети. Но там просто так сам не придумаешь. Макс поток не обязательно ходит по неперсекающимся путям. Пути могут частично пересекаться. во пример. ищем поток от вершины 1 к вершине 6. ребра (концы ребра и вес) 1 2 10 2 3 5 2 4 4 3 5 10 4 5 10 5 6 8 ОТвет: 8. 1

Определение максимальных потоков в сети

Решение