Dijkstra的algorthm修改 [英] Dijkstra's algorthm modification

问题描述

我知道了Dijkstra的最短路径算法。但是，如果我要修改它，而不是寻找最短路径，以便它会发现使用贪心算法的最长路径。什么我需要做下面的code：

I am aware of the Dijkstra's shortest path algorithm. However, if I were to modify it so that instead of finding the shortest path it would find the longest path using a greedy algorithm. What would I have to do to the code below:

下面是即时通讯使用的是什么：

Here is what Im using:

作为一个比较功能来选择最短路径版本正确的节点：

as a compare function to select the correct node in the shortest path version:

 if (Cost(potential_node) > Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

不过，去的另一面，这是不工作：

However, to get to the flip side this is not working:

 if (Cost(potential_node) < Cost(current_node) + cost(source , current_node)) then
 cost (potential_node) = cost(current_node) + cost (source, current_node)

糊涂一点，倒很AP preciate一些反馈

A bit confused, would really appreciate some feedback

推荐答案

在最长路径问题是 NP-硬的，并且因此没有已知的多项式溶液

The longest path problem is NP-Hard, and thus there is no known polynomial solution.

所建议的修改不工作，因为当Dijkstra算法标志着一个节点作为封闭意味着 - 绝不会有到它更短的路径。当试图做的最长的路径，如果你关闭一个节点的说法是不正确的 - 这并不意味着有它不再是路径

The suggested modification does not work, because when dijkstra's algorithm marks a node as "closed" it means - there will never be a shorter path to it. The claim is not true when trying to do it for longest path, if you closed a node - it doesn't mean there is no longer path to it.

回想一下，这正是我们证明对Dijkstra算法在每一步（更多的松弛不会找到任何更短的路径），但如果你发现一个电流路径最长使用midification一个顶点 - 这并不意味着这的确是最长的 - 有可能为一个最长的路径尚未探索

Recall that this is exactly what we prove on Dijkstra's algorithm at each step (more "relaxations" will not find any shorter path), but if you find a current longest path to a vertex using the midification - it doesn't mean it is indeed the longest one - there might be one longest path not yet explored.

修改 - 当它不工作（请原谅我，我是一个可怕的ASCII艺术家）反例

Edit - counter example when it doesn't work (forgive me I am a terrible ascii artist)

        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-＆GT; B-＆GT; C。的长度

Now, starting from A, this approach will first find C as the "longest path" and close it. From now on - there is no changes to C according to Dijkstra's algorithm, so you will conclude that the longest path from A to C is of length 2, while the path A->B->C is longer.

这篇关于Dijkstra的algorthm修改的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！