定义
最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:
(1)确定起点的最短路径问题- 即已知起始结点,求最短路径的问题。适合使用Dijkstra算法。(推荐学习:PHP视频教程)
(2)确定终点的最短路径问题- 与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
(3)确定起点终点的最短路径问题- 即已知起点和终点,求两结点之间的最短路径。
(4)全局最短路径问题- 求图中所有的最短路径。适合使用Floyd-Warshall算法 。
Dijkstra
求单源、无负权的最短路。时效性较好,时间复杂度为O(V*V+E)。源点可达的话,O(V*lgV+E*lgV)=>O(E*lgV)。
当是稀疏图的情况时,此时E=V*V/lgV,所以算法的时间复杂度可为O(V^2)。若是斐波那契堆作优先队列的话,算法时间复杂度,则为O(V*lgV + E)。
Floyd
求多源、无负权边的最短路。用矩阵记录图。时效性较差,时间复杂度O(V^3)。
Floyd-Warshall算法(Floyd-Warshall algorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题。
Bellman-Ford
求单源最短路,可以判断有无负权回路(若有,则不存在最短路),
时效性较好,时间复杂度O(VE)。
Bellman-Ford算法是求解单源最短路径问题的一种算法。
SPFA
是Bellman-Ford的队列优化,时效性相对好,时间复杂度O(kE)。(k<<V)。
与Bellman-ford算法类似,SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是,SPFA算法通过维护一个队列,使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点,从而大大减少了重复的操作次数。
更多PHP相关技术文章,请访问PHP图文教程栏目进行学习!
以上就是最短路径算法的详细内容,更多请关注php中文网其它相关文章!
![php中文网最新课程二维码](/static/images/article_wechat2021.jpg?1111)
声明:本文原创发布php中文网,转载请注明出处,感谢您的尊重!如有疑问,请联系admin@php.cn处理
网友评论
文明上网理性发言,请遵守 新闻评论服务协议
我要评论