Мне даны потоки-сеть G и их (реберные) емкости и (реберные) потоки через каждое ребро, а также поток F. Я хочу проверить, существует ли путь от источника к цели в остаточном графе, чтобы найти вне зависимости от того, является ли F максимальным расходом или нет.
Можно ли это сделать за время O(E)?
Может ли кто-нибудь дать мне некоторую помощь, и, может быть, показать, что я должен это сделать?
Мне даны потоки-сеть G и их (реберные) емкости и (реберные) потоки через каждое ребро. Я хочу проверить, существует ли путь от источника к цели.
Если вы только хотите проверить, существует ли путь от источника к цели, вам не нужен остаточный граф.
Если бы у меня был остаточный граф, я бы просто внес некоторые коррективы в алгоритм BFS, чтобы легко проверить, существует ли такой путь. Я обнаружил, что это можно сделать в O(|E|).
Временная сложность алгоритма BFS равна O(V+E), а не O(E).
Однако у меня нет остаточного графа, поэтому мой вопрос заключается в том, следует ли сначала вычислить его, а затем продолжить, и если да, то увеличит ли это мою общую временную сложность O (| E |)?
Вычисление остаточного графа должно занять больше времени, чем O(V+E).
Если вы пытаетесь решить проблему максимального потока, почему бы вам не использовать стандартные алгоритмы, такие как < href="https://en.wikipedia.org/wiki/Maximum_flow_problem" rel="nofollow noreferrer">алгоритм Форда-Фулкерсона, временная сложность которого равна O(E max|f|)?
Обновить
Я хочу проверить, существует ли путь от источника к цели в остаточном графе, чтобы узнать, является ли F максимальным потоком или нет. Можно ли это сделать за время O(E)?
Чтобы проверить, есть ли путь между двумя узлами в ориентированном графе, вам потребуется O(V+E) времени. Вы можете использовать либо BFS, либо DFS, как вы упоминали ранее в своем вопросе.
O(V+E). пожалуйста, посмотрите алгоритм из любого источника в Интернете. в любом случае, если граф не связан, вы не можете применить BFS в этом графе!
- person Wasi Ahmad; 20.02.2017
ford-fulkerson.
- person Wasi Ahmad; 20.02.2017
O(V+E). Вы можете использовать либо BFS, либо DFS, но вам понадобится O(V+E).
- person Wasi Ahmad; 20.02.2017
BFS можно использовать для поиска пути в остаточном графе. Запуск BFS требует O(|E|+|V|) времени выполнения. В потоковой сети все вершины связаны, поэтому количество вершин не больше, чем удвоенное количество ребер. С этой информацией запуск BFS для поиска пути в остаточном графе будет со сложностью O(|E|)
