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

Question

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

cgraphlongest-pathcyclic-graph

11

我已经解决了这里发布的大部分问题，除了最长路径问题。我读过有关最长路径的维基百科文章，如果图是无环的话，这似乎是一个简单的问题，但我的图不是无环的。

那么我该如何解决这个问题呢？采用蛮力法，检查所有可能的路径吗？我该如何开始做呢？

我知道对于一个具有约18000个节点的图形来说，这将需要很多时间。但是我仍然想开发它，因为这对于项目是必需品，我将在一个规模较小的图形上测试并展示给导师，其执行时间只需一两秒钟。

至少我完成了所有要求的任务，并且拥有一个可以运行的概念验证，但在循环图中没有更好的方式。但我不知道从哪里开始检查所有这些路径...

- rfgamaral

2

在循环图上，最长路径将是无限长度，不是吗？你只会一直绕来绕去... - qrdl

即使我标记了访问过的节点，那我为什么还会再次访问它们呢？这是我仍然无法理解的问题。在我的想象中，它应该像Dijkstra算法一样，只是“反着来”。就像下面建议的那样，但我无法使其正常工作。算法结束了，但结果似乎并不正确。 - rfgamaral

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted 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;
}

让我们手动在这个图上运行它：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 列表，以便能够存储指针并具有随机访问，因为您将需要它。例如，您可以保持 next[i] = node i 在其邻接列表中的下一个子节点，并相应地更新它。您可能会遇到一些边缘情况，并且可能需要不同的 end: 情况：一种正常情况，一种是当您访问已经访问过的节点时发生的情况，在这种情况下，指针不需要被重置。也许将 visited 条件移动到您决定将某些内容推送到堆栈之前，以避免这种情况。