解决办法就是暴力破解。你可以做一些优化来加速它,有些是微不足道的,有些是非常复杂的。我怀疑你能否让它在台式计算机上以足够快的速度运行 18,000 个节点,即使可以,我也不知道如何实现。然而,暴力破解的工作原理如下。
Note:如果您对确切的答案感兴趣,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:
情况:正常的一种情况和当您访问已经访问过的节点时发生的一种情况,在这种情况下不需要重置指针。也许在您决定将某些内容推入堆栈之前移动已访问的条件以避免这种情况。
明白为什么我说你不应该打扰吗? :)