1

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

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

4

1 回答 1

6

最长路径问题是NP-Hard ，因此没有已知的多项式解。

建议的修改不起作用，因为当 dijkstra 的算法将节点标记为“关闭”时，这意味着 - 永远不会有更短的路径。如果您关闭了一个节点，则在尝试最长路径时，该声明不正确 - 这并不意味着不再有通往该节点的路径。

回想一下，这正是我们在每个步骤中在 Dijkstra 算法上证明的（更多的“松弛”不会找到任何更短的路径），但是如果您使用 midification 找到当前最长的顶点路径 - 这并不意味着它确实是最长的一条 - 可能还有一条最长的路径尚未探索。

编辑 - 当它不起作用时的反例（请原谅我是一个糟糕的 ascii 艺术家）

        A
      /   \
     /     \
    1       2  
   /         \
  B-----5---> C
V = {A,B,C} ;  E = { (A,B,1), (A,C,2), (B,C,5) }

现在，从 开始A，这种方法将首先找到C“最长路径”并关闭它。C从现在开始 -根据 Dijkstra 的算法没有任何变化，因此您将得出结论，从Ato的最长路径C长度为 2，而路径A->B->C更长。

于 2012-10-12T17:10:59.443 回答