Потоковые сети - поиск # путей от заданной исходной вершины s до некоторой вершины t

Question

Мне было дано задание написать алгоритм, который находит # путей от s до t, образованных выделенными вершинами.

Exemple: рассмотрим ориентированный граф G = (V, E):

в данном примере ответ равен 2, один s, v, t или s, u, v, t и другой s, x, t

Я видел решение этой проблемы: сделать поток сети График G 'следующим образом:

где емкость дуг вида (i, i ') = 1 (i - некоторая вершина) и емкость дуг вида (i ', j) = бесконечность

говорят, что выполнение алгоритма Эдмондса Карпа на G 'выведет требуемый поток.

теперь я, кажется, не понимаю, как это решает проблему, я имею в виду, что если в первой итерации Эдмондс Карп случайно улучшит поток с помощью пути s, u, u ', v, v', x, x ' , т - в этом случае, как бы это исправить?

спасибо, впереди.

Answer 1

Как сетевой поток эквивалентен исходной проблеме :

=> , если есть n путей, они дадут поток n

<= </strong> если есть поток размером n , ребра с ненулевым потоком образуют n путей, каждая вершина используется не более одного раза, потому что емкость i-> i 'равна 1 (и ребра не выходят из i или заканчиваются в i')

не отвлекайтесь на бесконечную емкость, заданную для i-> j ребер, это также может быть 1 без изменения любого значения

Для описания всего алгоритма вам следует обратиться к некоторой литературе, например к этой , но путь, который вы пишете, не будет выбран первым из-за его длины , Алгоритм Эдмондса-Карпа начинается с кратчайших возможных путей.

Теперь (игнорируя этот факт) вы, вероятно, смущены тем фактом, что такой путь «блокирует» два других пути. Если такой путь (или комбинация путей) был выбран предыдущими итерациями, все равно будет увеличивающий путь , который будет использовать часть предыдущего пути в обратном направлении (sx-v'-t в вашем примере ).