我知道 Dijkstra 的最短路径算法。但是,如果我要修改它,而不是找到最短路径,而是使用贪婪算法找到最长路径。我需要对以下代码做什么:
这是我正在使用的:
作为在最短路径版本中选择正确节点的比较函数:
if (Cost(potential_node) > Cost(current_node) + cost(source , current_node)) then
cost (potential_node) = cost(current_node) + cost (source, current_node)
然而,从另一方面来说,这是行不通的:
if (Cost(potential_node) < Cost(current_node) + cost(source , current_node)) then
cost (potential_node) = cost(current_node) + cost (source, current_node)
有点困惑,非常感谢一些反馈
最佳答案
longest path problem是NP-Hard , 因此不存在已知的多项式解。
建议的修改不起作用,因为当 dijkstra 算法将节点标记为“关闭”时,这意味着 - 永远不会有更短的路径到达它。如果您关闭了一个节点,那么在尝试为最长路径执行此操作时,该声明是不正确的 - 这并不意味着不再有通往它的路径。
回想一下,这正是我们在 Dijkstra 算法的每一步中所证明的(更多的“松弛”不会找到任何更短的路径),但是如果您使用中化找到到顶点的当前最长路径 - 这并不意味着它确实是最长的 - 可能还有一条最长的路径尚未探索。
编辑 - 当它不起作用时反例(原谅我,我是一个糟糕的 ascii 艺术家)
A
/ \
/ \
1 2
/ \
B-----5---> C
V = {A,B,C} ; E = { (A,B,1), (A,C,2), (B,C,5) }
现在,从A
开始,这种方法将首先找到C
作为“最长路径”并将其关闭。从现在开始 - 根据 Dijkstra 算法,C
没有变化,因此您将得出从 A
到 C
的最长路径是长度为 2,而路径 A->B->C
更长。
关于algorithm - Dijkstra 算法修改,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12863818/