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

Question

我已经解决了大多数发布的问题 这里, ，除了最长的道路外，所有人都没有。我已经阅读了有关最长路径的Wikipedia文章，如果该图是无环，那么我的不是什么，这似乎有任何简单的问题。

那么如何解决问题？蛮力，检查所有可能的路径？我什至如何开始这样做？

我知道这将在〜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: 情况：当您访问已经访问的节点时发生的正常情况，在这种情况下，指针不需要重置。也许在决定在堆栈上推出一些东西以避免这种情况之前移动访问的状况。

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