Как найти путь увеличения графа

Question

Я пытаюсь реализовать алгоритм Форда-Фулкерсона для вычисления максимального потока в сети потоков.

Один шаг алгоритма состоит в том, чтобы найти путь от начального узла до конечного узла (также известный как сток ) с доступной емкостью по всем ребрам.

Не могли бы вы предложить простой и понятный способ найти путь расширения ?

ОБНОВЛЕНИЕ № 1:

Моя функция BFS:

template <class T>
vector<Vertex<T> *> Graph<T>::bfs(T source) const {
    vector<Vertex<T> *> path;
    queue<Vertex<T> *> q;
    Vertex<T> * v = getVertex(source);
    q.push(v);
    v->visited = true;
    while (!q.empty()) {
        Vertex<T> *v1 = q.front();
        q.pop();
        path.push_back(v1);
        typename vector<Edge<T> >::iterator it = v1->adj.begin();
        typename vector<Edge<T> >::iterator ite = v1->adj.end();
        for (; it!=ite; it++) {
            Vertex<T> *d = it->dest;
            if (d->visited == false) {
                d->visited = true;
                q.push(d);
            }
        }
    }

    return path;
}

Это неправильно / неполно, так как возвращает неправильные результаты. Я думаю, что подделываю что-то.

Answer 1

Читать здесь .В основном используйте Breadth-first_search .

Редактировать: path.push_back(v1); не в том месте.Вы добавите все вершины графа в путь.Правильный способ - хранить для каждого узла, который является узлом-предшественником.Таким образом, вы можете восстановить найденный путь.Также вы можете нарушить условие while, достигнув раковины.

if (d->visited == false) {
    d->visited = true;
    q.push(d);
    predecessor[d] = v1;
}

Answer 2

Немного сложно дать вам четкий совет, не зная базовых структур данных. Обычно, когда вы имеете дело с потоками, у вас есть орграф. Я приму это за мой ответ. Теперь я вижу несколько серьезных проблем и одно незначительное замечание:

template <class T>
vector<Vertex<T> *> Graph<T>::bfs(T source) const {
    vector<Vertex<T> *> path;   

В этом случае лучше использовать список, поскольку векторы имеют только амортизированное постоянное время вставки и удаления, тогда как списки действительно постоянны. (Предполагается, что вы имеете в виду STL-контейнеры) - это было незначительное замечание;)

    queue<Vertex<T> *> q;

Для BFS у вас есть два варианта: либо сохранить все пути, либо сохранить предшественник для каждой вершины после ее посещения. Вы просто сохраняете вершины, которые вам нужно посетить. Таким образом, я не понимаю, как вы сможете восстановить полный путь, как только доберетесь до раковины.

    Vertex<T> * v = getVertex(source);
    q.push(v);
    v->visited = true;

Мне кажется, что инициализация в порядке.

    while (!q.empty()) {
        Vertex<T> *v1 = q.front();
        q.pop();
        path.push_back(v1);
        typename vector<Edge<T> >::iterator it = v1->adj.begin();
        typename vector<Edge<T> >::iterator ite = v1->adj.end();

Здесь вы берете список смежности вершины, в которой вы сейчас находитесь. Помните, однако, что пути расширения называются дополнением, потому что вы можете пересечь ребро либо вперед (если есть оставшаяся емкость, таким образом, текущий поток через это ребро меньше, чем емкость ребра), либо назад (если текущий поток через это край больше 0). Вы просто берете все ребра, которые идут вперед на графике, и посещаете их. Это «нормальная» BFS, а не BFS, адаптированная к разной структуре графов, используемой в задачах с максимальным потоком.

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

        for (; it!=ite; it++) {
            Vertex<T> *d = it->dest;
            if (d->visited == false) {
                d->visited = true;
                q.push(d);
            }
        }
    }

Эта часть выглядит хорошо для меня, за исключением пунктов, которые я уже упоминал. Итак - сохраните предшественники, проверьте, полезен ли путь для максимального потока (осталась ли емкость), а также проверьте обратные дуги.

    return path;

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

Последнее замечание: Для Ford-Fulkerson может оказаться разумной идеей вычислить значение, с которым вы можете увеличивать поток на текущем пути непосредственно при выполнении BFS. Таким образом, вам не нужно посещать края еще раз. Конечно, вы могли бы сделать это, собирая путь, используя еще не сохраненные предшественники.

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

Answer 3

Посмотрите на исходный код: здесь он http://aduni.org/courses/algorithms/courseware/handouts/Reciation_09.html