Описание тега edmonds-karp

Вопросы с тегом
The Edmonds-Karp algorithm is a polynomial-time algorithm for finding the maximum flow in a flow network.
0 ответов

Почему Эдмонд Карпс быстрее, чем Форд-Фулкерсон?

Почему выбор кратчайшего пути дополнения каждый раз вместо произвольного пути дополнения делает алгоритм Эдмонда Карпса быстрее, чем Ford-Fulkerson
14 янв '15 в 20:50
0 ответов

Как вы находите максимальный поток на орграфе, где возможности могут быть отрицательными?

Ford-Fulkerson и Edmonds-Karp et. и др. начните с нулевого потока и увеличивайте его до тех пор, пока он не может быть увеличен. В случае положительных способностей; однако начальный нулевой поток гарантированно будет как законным потоком, так и пот…
13 сен '13 в 16:43
1 ответ

Создание графика производительности алгоритма максимального потока Эдмондса Карпа в Python

Прежде чем я углублюсь в вопрос, вот некоторая справочная информация о том, что у меня уже есть: - Сначала я создал матрицу ненаправленной матрицы смежности, основанную на городах по всей территории США, где веса ребер были рассчитанным расстоянием …
03 дек '12 в 04:27
1 ответ

Максимальный поток Линейный алгоритм времени, Найти правильный поток

Итак, позвольте мне объяснить вопрос: Вам дан график. Вы найдете максимальный поток. Но оказывается, что у края, e_i, была неправильная способность. Это был один меньше. К сожалению, поток был максимизирован на старой мощности. Вычислите новый макси…
17 сен '13 в 00:00
0 ответов

Сложность алгоритма Чу-Лю-Эдмондса

Мы легко можем найти в интернете, что сложность алгоритма Чу Лю Эдмондса для нахождения лучшего MST в ориентированном графе - это O(V*E). Кто-нибудь может объяснить, как получается этот результат?
12 янв '19 в 21:25
1 ответ

С реализация алгоритма разрешения потока с невзвешенными двунаправленными ребрами и узлами с пропускной способностью

Я попытался найти переполнение стека для ответа на мой вопрос. Я нашел эти ответы, но их решение не относится к моему делу, так как у меня есть ненаправленные края. Я не могу создать новую вершину с ребрами, идущими в Vin, и ребрами, идущими в Vout,…
01 мар '18 в 08:52
1 ответ

Как разорвать связь в кратчайшей длине увеличения в алгоритме Эдмондса-Карпа?

Итак, если 2 кратчайших пути дополнения имеют длину 2, что такое вторичный фильтр? Из того, что я понимаю, Эдмондс-Карп выбирает кратчайший путь, то есть путь с наименьшим количеством ребер. Однако оба эти пути имеют длину 2. Таким образом, этот алг…
14 июл '16 в 18:49
1 ответ

Отсутствует несколько путей в алгоритме Эдмондса Карпа Макса

Я бы реализовал алгоритм Эдмонда Карпа, но, похоже, он не правильный, и я не получаю правильный поток, рассмотрим следующий график и поток от 4 до 8: Алгоритм работает следующим образом: Сначала находит 4→1→8, затем находит 4→5→8 после этого 4→1→6→8…
25 фев '12 в 15:38
1 ответ

Использование именованных параметров и свойств Bundled с edmonds_karp_max_flow()

Я пытаюсь использовать именованные параметры со свойствами Bundled в edmonds_karp_max_flow алгоритм библиотеки Boost-графов. Чтобы показать мою проблему, я взял существующий пример edmonds-karp и превратил свойства Internal в свойства Bundled (я наз…
03 июн '15 в 13:16
2 ответа

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

Предположим, что у нас есть поток в сети и, используя алгоритм Эдмонда-Карпа, у нас уже есть максимальный поток в сети. Теперь, если мы добавим произвольное ребро (с определенной пропускной способностью) в сеть, каков наилучший способ обновления мак…
13 дек '14 в 05:47
0 ответов

MaxFlow - получаю неправильный ответ - не знаю почему

Я пытаюсь решить эту проблему (назначить задачи, которые соответствуют некоторым из ряда категорий категориям, чтобы каждая категория содержала требуемое количество проблем), используя алгоритм максимального потока (Edmonds-Karp), и я получаю неправ…
09 авг '15 в 15:41
1 ответ

Алгоритм Эдмондса Карпа и 0 1 возможностей

Какова верхняя граница Эдмондса Карпа (BFS), когда единственными доступными мощностями являются 0 и 1? Я не понимаю разницы, когда емкости только 0 и 1, я знаю, что Ford Fulkerson находит, что значение потока равно 0 или 1, если емкости 0 и 1. Помог…
05 июн '12 в 19:12
2 ответа

3 максимальный поток доказать или опровергнуть небольшие вопросы

Вопросы: поскольку (а) кажется, что это не так, мы можем найти пример роста потока без насыщения е. для (б) это кажется правдой, но я не уверен, как это доказать. Может быть, из-за минимального среза максимального расхода, он был на минимальном срез…
07 янв '16 в 16:29
0 ответов

Что значит увеличить поток?

Когда алгоритм Эдмондса-Карпа говорит об увеличении потока f вдоль пути p, что на самом деле означает увеличение потока? Означает ли это отправить поток вдоль пути?
05 июл '16 в 21:56
1 ответ

Максимальный поток в невзвешенном графике

Проблема максимального потока обычно решается с помощью алгоритма Эдмонда-Карпа, который строит остаточный граф и использует BFS для поиска путей расширения. Но обычно проблема максимального потока определяется для взвешенного графа. Для невзвешенно…
21 фев '17 в 20:04
2 ответа

Форд-Фулкерсон реализация java

Я пытаюсь научиться реализовывать алгоритм Форда-Фулкерсона в Java и нашел некоторую помощь в Интернете, но я застрял в этом фрагменте кода // update residual capacities of the edges and // reverse edges along the path for (v=t; v != s; v=parent[v])…
14 апр '16 в 07:28
0 ответов

Почему элементы в моем heapq не упорядочены по python?

Я использую простой heapq в python с пользовательскими элементами, на которых я реализовал функцию lt. class Edge: def __init__(self, cost, u, v): self.u = u self.v = v self.cost = cost def weight(self): w = self.cost v = self.v while v.parent is no…
04 окт '18 в 13:19
0 ответов

Какой алгоритм назначения я должен использовать?

У меня есть один набор, и мне нужно создать пары из двух элементов из этого набора. Все задания взвешены. Сопоставление должно быть либо сжатым, либо идеальным, в зависимости от результатов. Я предполагаю, что мне нужно взвешенное сопоставление в об…
21 май '17 в 21:26
0 ответов

Почему сложность алгоритма Эдмондса-Карпа меньше, чем у алгоритма Форда-Фулкерсона?

Форд Фулкерсон сложность O(FE), но Эдмонд Карпс O(VE^2), Это основано на предпосылке, что каждый край может быть только критическим O(V) количество раз, и это относится ко всему краю, поэтому мы имеем O(VE) количество раз, когда ребро может стать кр…
30 мар '18 в 14:03
1 ответ

Как алгоритм Эдмондса-Карпа на самом деле вычисляет кратчайший путь?

Я пытаюсь понять алгоритм Эдмондса-Карпа более подробно, и мне было интересно узнать, какой алгоритм он использует для вычисления кратчайшего пути (наименьшего числа ребер) от s до t для каждой итерации
03 апр '14 в 08:24