Dijkstra与SPFA算法的不同之处对比
184 浏览量
2021-01-07
05:09:15
上传
评论 1
收藏 63KB PDF 举报
Dijkstra与与SPFA算法的不同之处对比算法的不同之处对比
SPFA算法
此处为SPFA算法详解
用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为
INF。将源点入队，并重复以下步骤：
1、队首x出队
2、遍历所有以队首为起点的有向边(x,i)，若dis[x]+w(x,i)<dis[i]，则更新dis[i] 3、如果点i不在队列中，则i入队
4、若队列为空，跳出循环；否则执行1
Dijkstra算法
此处为Dijkstra算法详解
清除所有点的标号;
设d[0]=0，其他d[i]=INF;//INF是一个很大的值，用来替代正无穷
循环n次 {
在所有未标号结点中，选出d值最小的结点x;
给结点x标记;
对于从x出发的所有边(x,y)，更新d[y] = min{d[y], d[x]+w(x,y)}
二者最主要的区别在于：二者最主要的区别在于：
SPFA算法可以处理带负权的边，而Dijkstra算法不行。
Dijkstra算法采用贪心策略，每次选择距当前最近的点进行延伸（贪心，不公平），但贪心往往只能求得局部最优解，如下
图，用Dijkstra算法的话，显然1->2是当前的最短路径；
SPFA算法类似于bfs，属于同一层次的结点都会遍历到（公平），它求得的的最短路径是1->3->2。
资源评论
