如何在两个节点之间的循环图中找到最长的路径? [英] How do find the longest path in a cyclic Graph between two nodes?

问题描述

我已经解决了大多数问题，此处，除最长路径外的所有路径.我已经阅读了有关最长路径的Wikipedia文章，如果该图是非循环的，那似乎不是一个容易的问题，而我的不是.

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?

我知道它将以大约18000的价格占用很多图表.但无论如何，我只是想开发它，因为它是项目所必需的，所以我将对其进行测试，并在较小的比例图上将其显示给讲师，该图的执行时间仅为一两秒.

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.

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

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...

推荐答案

解决方案是对其进行暴力破解.您可以进行一些优化以加快速度，一些是微不足道的，有些则非常复杂.我怀疑您能否使其足够快地运行于台式计算机上的18 000个节点，即使您不知道如何运行也是如此.但是，这是暴力破解的工作方式.

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.

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

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

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'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)

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

(*)-这有点问题-您必须为每个节点保留指向下一个子节点的指针，因为它可以在while循环的不同迭代之间进行更改，甚至会重置自身(当您将topStack.node节点弹出堆栈，因此请确保将其重置).这在链接列表上最容易实现，但是您应该使用int[]列表或vector<int>列表，以便能够存储指针并具有随机访问权限，因为您将需要它.您可以保留例如next[i] = next child of node i in its adjacency list并相应地进行更新.您可能会遇到一些极端情况，并且可能需要使用不同的end:情况:一种正常的情况是在您访问已访问的节点时发生的，在这种情况下，无需重置指针.也许在决定将某些内容推入堆栈之前先移动已访问的条件，以避免发生这种情况.

(*) - 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.

明白为什么我说你不应该打扰吗? :)

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

这篇关于如何在两个节点之间的循环图中找到最长的路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！