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

我已经解决了大部分的问题,除了最长的路径问题我读过维基百科上关于最长路径的文章,如果图是非循环的,似乎任何问题都很容易解决,而我的不是。
那我该怎么解决这个问题呢?暴力,通过检查所有可能的路径?我该怎么做呢?
我知道在一张有约18000人的图表上要花很多钱。但我只是想开发它,因为它是项目所必需的,我只需要测试它,并在一个较小的比例图上显示给讲师,其中执行时间只有一两秒钟。
至少我完成了所有需要的任务,我有一个概念的运行证明,它可以工作,但没有更好的方法在循环图上。但我不知道从哪里开始检查这些路径…


最佳答案:

解决办法是用暴力来强迫它。你可以做一些优化来加速它,有些是微不足道的,有些是非常复杂的我怀疑你能让它在桌面计算机上工作足够快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:情况:正常情况和访问已访问的节点时发生的情况,在这种情况下,不需要重置指针在决定将某个东西推到堆栈上之前,可以移动访问的条件以避免出现这种情况。
明白我为什么说你不该麻烦了吗:)

译文:来源   文章分类: c graph cyclic longest-path

相关文章:

c - 如何在C的结构成员中扫描带有空格的字符串?

c - 在传递语句参数之前初始化变量如何影响输出?

c++ - Win32 Sleep()在游戏循环中的准确性

c - 简单的C程序可在OS X上编译,但不能在Fedora 16上编译,但包含math.h但未使用

c - 在C中编译套接字连接代码时出现问题

c - 循环获取主机,网络,协议和服务数据库中的多个条目

c - 如何找到给定边长的斜角四面体的面角

c - 在OS X上从C中的dlopen()动态库访问主程序全局变量

c - 如何在没有目录迭代的情况下在Linux上获取区分大小写的路径?

c - 将char安全地转换为整数