Dijkstra的algorthm修改

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

的最长路径问题是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"最长的路径"并关闭它.从现在开始 - C根据Dijkstra的算法没有变化,因此您将得出结论:从最长路径A到C长度为2,而路径A->B->C更长.