algorithm - Dijkstra 算法修改

Question

我知道 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)

有点困惑，非常感谢一些反馈

Answer 1

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 更长。