Как найти самый длинный путь в циклическом графе между двумя узлами? - PullRequest
Новая
       32

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

10 голосов
/ 21 апреля 2010

Я уже решил большинство вопросов, размещенных здесь , все, кроме самого длинного пути.Я читал статью в Википедии о самых длинных путях, и кажется, что если график был ациклическим, то возникла какая-то легкая проблема, а у меня - нет.Грубая сила, проверяя все возможные пути?Как мне вообще начать это делать?

Я знаю, что будет много на графике с ~ 18000.Но я все равно хочу его разработать, потому что это требуется для проекта, и я просто протестирую его и покажу инструктору на мелкомасштабном графике, где время выполнения составляет всего секунду или две.По крайней мере, я выполнил все необходимые задачи, и у меня есть действующее доказательство того, что это работает, но лучшего способа на циклических графах нет.Но я понятия не имею, с чего начать проверять все эти пути ...

1 Ответ

8 голосов
/ 22 апреля 2010

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

Примечание: Дейкстра и любые другие алгоритмы кратчайшего пути НЕ будут работать для этой проблемы, если вы заинтересованы в точном ответе. 

Start at a root node *root*
Let D[i] = longest path from node *root* to node i. D[*root*] = 0, and the others are also 0.

void getLongestPath(node, currSum)
{
    if node is visited
        return;
    mark node as visited;

    if D[node] < currSum
        D[node] = currSum;

    for each child i of node do
        getLongestPath(i, currSum + EdgeWeight(i, node));

    mark node as not visited;
}

Давайте запустим это вручную на этом графике: 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)

Let the root be 1. We call getLongestPath(1, 0);
2 is marked as visited and getLongestPath(2, 4); is called
D[2] = 0 < currSum = 4 so D[2] = 4.
3 is marked as visited and getLongestPath(3, 4 + 5); is called
D[3] = 0 < currSum = 9 so D[3] = 9.
4 is marked as visited and getLongestPath(4, 9 + 7); is called
D[4] = 0 < currSum = 16 so D[4] = 16.
5 is marked as visited and getLongestPath(5, 16 + 1000); is called
D[5] = 0 < currSum = 1016 so D[5] = 1016.
getLongestPath(3, 1016 + 200); is called, but node 3 is marked as visited, so nothing happens.
Node 5 has no more child nodes, so the function marks 5 as not visited and backtracks to 4. The backtracking will happen until node 1 is hit, which will end up setting D[3] = 100 and updating more nodes.

Вот как это выглядит итеративно (не проверено, просто базовая идея): 

Let st be a stack, the rest remains unchanged;
void getLongestPath(root)
{
    st.push(pair(root, 0));

    while st is not empty
    {
        topStack = st.top();
        if topStack.node is visited
            goto end;
        mark topStack.node as visited;

        if D[topStack.node] < topStack.sum
            D[topStack.node = topStack.sum;

        if topStack.node has a remaining child (*)
            st.push(pair(nextchild of topStack.node, topStack.sum + edge cost of topStack.node - nextchild)) 

        end:
        mark topStack.node as not visited
        st.pop();
    }
}

(*) - это небольшая проблема - вам нужно сохранить указатель на следующий дочерний элемент для каждого узла, так как он может переключаться между различными итерациями цикла while и даже сбрасывать сам себя (указатель сбрасывается, когда Вы вытаскиваете узел topStack.node из стека, поэтому обязательно его сбросьте). Это проще всего реализовать в связанных списках, однако вы должны использовать либо списки int[], либо списки vector<int>, чтобы иметь возможность хранить указатели и иметь произвольный доступ, поскольку он вам понадобится. Вы можете оставить, например, next[i] = next child of node i in its adjacency list и обновить его соответствующим образом. У вас могут быть некоторые крайние случаи, и вам могут потребоваться другие end: ситуации: обычная и та, которая происходит, когда вы посещаете уже посещенный узел, и в этом случае указатели не нужно сбрасывать. Возможно, передвиньте посещенное условие, прежде чем вы решите поместить что-либо в стек, чтобы избежать этого.

Видишь, почему я сказал, что тебе не стоит беспокоиться? :)

...