回 帖 发 新 帖 刷新版面

主题:关于Dijkstra算法

如果要把计算最短路径改成计算最长路径,是不是把代码改成如下就可以了
   if(map[i][j]<map[i][k]+map[k][j])
       map[i][j]=map[i][k]+map[k][j];

回复列表 (共2个回复)

沙发

最长路径?你的想法还真怪,如果不要求是真路的话,有可能没有最长路径,或者说无穷大,如果只考虑真路,当然是如果能包含所有结点的路有可能最长,如果存在,就是哈密顿路,这跟最短哈密顿环问题类似,在这些哈密顿路中的偏序关系中求最值.如果不存在整个图的哈密顿路,那一定存在它的某个子图存在,问题更复杂一些.
而不是从Dijkstra算法中这么简单改改就解决的问题我觉得.

板凳

我来回复

您尚未登录,请登录后再回复。点此登录或注册