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

Question

我已经解决了这里发布的大多数问题,除了最长的路径之外.我已经读过关于最长路径的维基百科文章,如果图表是非循环的,那么这似乎是一个简单的问题.

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

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

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

Answer 1

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

注意:如果您对确切答案感兴趣,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;
}

让我们在这张图上手动运行它: 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:情况:正常的情况和访问已访问的节点时发生的情况,在这种情况下指针不需要重置.也许在您决定在堆栈上推送某些东西之前移动访问条件以避免这种情况.

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