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

Question

我已经解决了大部分问题here，都是最长的路径之一。我已阅读维基百科有关最长路径的文章，如果图形是非循环的，它似乎是一个简单的问题，而我并不是。

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

我知道它会在一个图表上拍一大堆〜18000。但我只是想要开发它，因为它是项目所需的，我只需测试它并将其显示给指导者，其中执行时间仅为一秒或两秒。

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

Answer 1

解决方案是蛮横的。你可以做一些优化来加速它，有些是微不足道的，有些是非常复杂的。我怀疑你可以在桌面计算机上为18000个节点快速运行，即使你不知道如何。这是bruteforce的工作方式。

备注：如果您对确切答案感兴趣，那么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循环的不同迭代之间进行更改，甚至可以自行重置（当您弹出时指针会自动复位e topStack.node节点离开堆栈，因此请务必将其重置）。这在链表上最容易实现，但是您应该使用int[]列表或vector<int>列表，以便能够存储指针并具有随机访问权限，因为您需要它。您可以保留例如next[i] = next child of node i in its adjacency list并相应地更新。您可能会遇到一些边缘情况，可能需要不同的情况：正常情况和访问已访问节点时发生的情况，在这种情况下，指针不需要重置。也许在决定推入堆栈之前移动访问条件以避免这种情况。

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