如何在两个节点之间找到循环图中最长的路径？

I already solved most the questions posted here, all but the longest path one. I've read the Wikipedia article about longest paths and it seems any easy problem if the graph was acyclic, which mine is not.

我已经解决了这里发布的大多数问题,除了最长的路径之外。我已经阅读了关于最长路径的*文章,如果图形是非循环的,那么这似乎是一个简单的问题,而我的不是。

How do I solve the problem then? Brute force, by checking all possible paths? How do I even begin to do that?

那我怎么解决这个问题呢?蛮力,通过检查所有可能的路径?我怎么开始这样做?

I know it's going to take A LOT on a Graph with ~18000. But I just want to develop it anyway, cause it's required for the project and I'll just test it and show it to the instructor on a smaller scale graph where the execution time is just a second or two.

我知道它会在图表上获得很多~18000。但我只是想开发它,因为它是项目所需要的,我只是测试它并在一个较小比例的图形上向教师显示,执行时间只有一两秒钟。

At least I did all tasks required and I have a running proof of concept that it works but there's no better way on cyclic graphs. But I don't have clue where to start checking all these paths...

至少我完成了所有必需的任务,并且我有一个运行的概念证明它可以工作但是在循环图上没有更好的方法。但我不知道从哪里开始检查所有这些路径......

1 个解决方案

#1

The solution is to brute force it. You can do some optimizations to speed it up, some are trivial, some are very complicated. I doubt you can get it to work fast enough for 18 000 nodes on a desktop computer, and even if you can I have no idea how. Here's how the bruteforce works however.

解决方案是暴力破解它。你可以做一些优化来加速它,有些是微不足道的,有些是非常复杂的。我怀疑你可以让它在桌面计算机上足够快地工作18 000个节点,即使你我不知道如何。然而,这是暴力行为的工作方式。

Note: Dijkstra and any of the other shortest path algorithms will NOT work for this problem if you are interested in an exact answer.

注意:如果您对确切答案感兴趣,Dijkstra和任何其他最短路径算法都不适用于此问题。

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;
}

Let's run it by hand on this graph: 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)

让我们在这张图上手动运行它: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.

Here's how it would look iteratively (not tested, just a basic idea):

这是迭代看的方式(未经测试,只是一个基本想法):

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();
    }
}

(*) - this is a bit of a problem - you have to keep a pointer to the next child for each node, since it can change between different iterations of the while loop and even reset itself (the pointer resets itself when you pop the topStack.node node off the stack, so make sure to reset it). This is easiest to implement on linked lists, however you should use either int[] lists or vector<int> lists, so as to be able to store the pointers and have random access, because you will need it. You can keep for example next[i] = next child of node i in its adjacency list and update that accordingly. You might have some edge cases and might need to different end: situations: a normal one and one that happens when you visit an already visited node, in which case the pointers don't need to be reset. Maybe move the visited condition before you decide to push something on the stack to avoid this.

(*) - 这有点问题 - 您必须为每个节点保留一个指向下一个子节点的指针,因为它可以在while循环的不同迭代之间进行更改,甚至可以自行重置(当您弹出时,指针会自行重置topStack.node节点离开堆栈,所以一定要重置它)。这在链表上最容易实现,但是您应该使用int []列表或vector 列表,以便能够存储指针并具有随机访问权限,因为您将需要它。例如,您可以在其邻接列表中保留next [i] =节点i的下一个子节点并相应地更新它。您可能有一些边缘情况并且可能需要不同的结束:情况:正常的情况和当您访问已访问的节点时发生的情况,在这种情况下指针不需要重置。也许在您决定在堆栈上推送一些内容之前移动访问条件以避免这种情况。

See why I said you shouldn't bother? :)

看看为什么我说你不应该打扰? :)

#1