第一种,bellman-ford算法;
算法:求单源的两点间最短路。
过程:每次枚举所有已知的边,更新一个点到源点的最短距离,重复V-1次,即可找到各个点离源点的最短距离。
证明:对于从源点出发到任意一点,最差的情况就是算出了前面所有点的最短距离,才能求出该点的最短距离,即把该点看成是V,起点看成是1,那么这两点间最多有V-1条边,对于每条边上的端点,都需要枚举所有的边数E,才能算出该端点距起点1的最短距离。
所以该算法的复杂度为:O(VE). 但是可以用来判断是否存在正环负环,即判断第V次是否还继续更新最短距离。
第二种,DIJ算法.
算法:求单源的两点的最短路。
过程:每次找到最短距离已经确定的点(即在未知的点中与源点距离最短的点),从它出发更新相邻定点的最短距离。此后不需要再关心刚才那个“最短距离已经确定的定点”,重复这两个操作,直到所有点都被确定。
证明:每次遍历used[i]==0的顶点,找到与源点的最短距离d[i]最短的那个点,作为已知点,记为used[i]=1,并进行扩散,更新与它相邻的点的最短距离。为什么呢,因为在未知的点中,每次的那个与源点最近的点,已经不能找到比这个距离更短的边去表示它了,所以这个顶点与源点的最短距离,就是它了。一共要确定V个点,循环V次。
所以该算法的复杂度为:O(V^2)。但是可以用堆来优化,在每次找与源点距离最短的点时,可以用堆来找到最小值。
这样,复杂度就变成了O(ElogV);
第三种,floyd-warshall算法.
算法:求任意两点的最短路。
DP方程:d[k][i][j]表示只使用1~k的顶点和i和j,从顶点i到顶点j的最短路。
递推过程:只使用1~k时,我们分i到j的最短路正好经过顶点k一次和完全不经过顶点k两种情况来讨论。
不经过顶点k的情况下,d[k][i][j] = d[k - 1][i][j];
通过顶点k的情况下,d[k][i][j] = d[k - 1][i][k] + d[k - 1][k][j];
合起来,就可以得到
d[k][i][j] = min(d[k - 1][i][j], d[k - 1][i][k] + d[k - 1][k][j]).
当然,因为k表示的含义比k - 1更广,因此,把第一维数组都用成k的话,那就可以将dp方程简化为:d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
代码实现:
int i, j, k;
for (k = 1; k <= V; ++k)
{
for (i = 1; i <= V; ++i)
{
for (j = 1; j <= V; ++j)
{
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
所以该算法的复杂度是O(V^3),是比较高的了,但也可以判断是否存在负环,只需要判断是否存在d[i][j]是负数即可。
综上,单源最短路有Bellman和Dij算法,可判断负环的是Bellman和Floyd算法,求任意两点最短路的只有Floyd算法。可根据实际情况来选用。
分享到:
相关推荐
图论matlab实现,各种图论的求解,最短路、哈密尔顿回路等等
图论第四章 最短路算法(研究生).ppt 图论第四章 最短路算法(研究生).ppt
最短路 图论 算法 图论中的最短路问题一些问题,求解方法。。。。。。。。。。。
最短路算法prim算法图论最短路应该没什么好说的吧
图论Dijkstra最短路算法matlab通用程序,有实例。希望对大家有用
图论课件--最短路算法、图和代数表示.ppt
本程序是使用c++编写的最短路算法,需要输入的是一个graph的阶数以及赋权矩阵
图论最短路dijkstra算法.doc
不用多说最短路估计学算法的一定不会陌生了吧,但是网上资源比较杂很难找到好的,这是我学习看的希望对你们有所帮助。
图论- 最短路.rar
这是运用C++求出来的第k短路,属于图论
2022级图论-欧拉回路和最短路_题解
最短路(图论)1
图论入门与最短路_黄哲威.pdf
用编好的Floyd程序求最短路径,只要画出点和路线,就可以自动计算出最短路径
图论模型最短路PPT教案.pptx
图论中最短路算法及其应用.doc
图论--最短路算法、图和代数表示.ppt
图论- 最短路- Johnson 算法.rar
图论- 最短路- Floyd 算法.rar