Найти путь от источника к цели в остаточном графе графика сетевого потока за O(E) время

Question

Мне дана сеть потоков G и их (ребро) Емкости и (ребро) потоки через каждое ребро, а также Поток F. Я хочу проверить, существует ли путь от источника к цели в остаточном графе, чтобы найти вне, если F является максимальным потоком или нет.

Можно ли сделать это за O(E) время?

Может ли кто-нибудь мне помочь, и, может быть, покажет, что я должен это сделать?

• Был отредактирован

Answer 1

BFS можно использовать для поиска пути в остаточном графе. Для запуска BFS требуется время работы O(|E|+|V|). В потоковой сети все вершины соединены, поэтому количество вершин не превышает двойного количества ребер. С этой информацией запуск BFS для поиска пути в остаточном графе выполняется со сложностью O(|E|)

Answer 2

Мне дана сеть потоков G и их (ребро) Емкости и (ребро) потоки через каждое ребро. Я хочу проверить, существует ли путь от источника к цели.

Если вы хотите только проверить, существует ли путь от источника к цели, тогда вам не нужен остаточный граф.

Если бы у меня был остаточный граф, я бы просто внес корректировку в алгоритм BFS, чтобы легко проверить, существует ли такой путь. Я обнаружил, что это можно сделать в O(|E|).

Временная сложность алгоритма BFS составляет O(V+E)не O(E),

Однако у меня нет остаточного графа, поэтому мой вопрос: стоит ли сначала его вычислять, а затем продолжить, и если да, увеличит ли это мою общую сложность по времени O(|E|)?

Вычисление остаточного графа должно занять больше времени, чем O(V+E),

Если вы пытаетесь решить проблему максимального потока, почему бы вам не использовать стандартные алгоритмы, такие как алгоритм ford-fulkerson, сложность которого равна O(E max|f|)?

---

Обновить

Я хочу проверить, существует ли путь от источника к цели в остаточном графе, чтобы выяснить, является ли F максимальным потоком или нет. Можно ли сделать это за O(E) время?

Чтобы проверить, существует ли путь между двумя узлами в ориентированном графе, вам нужно O(V+E) время. Вы можете использовать BFS или DFS, как вы упоминали ранее в своем вопросе.