最长路【模板】

1.dijkastra 是不可行的

如果选取dijkstra求取最长路,那么思想肯定就是选取当前权值最大的点,并且选取最长的路径。但是这种思想是错误的!我们从源点来举个例子。a—b c表示的是a,b之间的路径长度为c

12 2

13 1

34 1

42 1

我们的目的是求解1到2这两个点之间的最小距离。然后说一下步骤

    我们先将1的路径权值标记为0,然后压入优先队列
    然后1出队,更新2,3。将2,3压入队。
    然后我们会选取优先队列里面权值较大的2出队列,用2来更新4。
    好了,接下来就没有结点2的事情了,但是此时2到0的最长距离就定格在2。但实际上最长路应该是3.


————————————————
版权声明:本文为CSDN博主「Salix_」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_41755258/article/details/85015285
View Code

2.floyed和bellman—ford

直接将所有的边都取负,然后按照最短路求解就行了。但是对于有环出现的情况,floyed就不行了,我们就需要借助bellman算法来判负环。

    floyed的实质是动态规划,不能处理负环。如果点的数量不是特别多的话,可以使用深搜(通过vis数组标记,看是否会遍历到之前已经遍历过的点)。如果点的个数非常多的话,就得使用ford或者是spfa。
    bell—ford可以处理负环,也是通过判断松弛的次数是不是超过了N次。


————————————————
版权声明:本文为CSDN博主「Salix_」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_41755258/article/details/85015285
View Code

例题:

1.Job Hunt S

【我的代码有参考价值】

原文地址:https://www.cnblogs.com/bear-xin/p/14949907.html