Dijkstra
2024-06-29 20:31:39
发布于:浙江
最短路算法
单源最短路算法
一个起点到达其他所有顶点的 最短距离
多源最短路算法
任意两点之间的最短距离
Dijkstra
单源最短路算法
缺点:假如出现负权值的边,那么就无法求得正确的答案。
核心思想:贪心原则,从起点出发,优先选择距离起点最近的顶点来作为下一个松弛的顶点,最终松弛完所有顶点。
松弛:某个顶点作为中转站,使得起点到达这个点相邻顶点的距离变得更短。
Dij基本代码框架
int dis[MAX_N]; // 保存起点到任意顶点的距离
bool vis[MAX_N] ; // 标记数组标记哪个顶点被松驰过
void dij(){
// 3、循环n次松弛n个顶点
for(int i = 0 ; i < n ; i ++ ){
// 1、 找到最近的顶点最为松弛顶点
int pos = 0; // 假设顶点从1开始,一开始设置为0代表不存在
for(int j = 1 ; j <= n ; j ++ ){
if(!vis[j] && dis[j] < dis[pos]){
pos = j ; // 假如有距离起点更近的顶点,那么选择它
}
}
vis[pos]=true;
// 2、进行松弛,更改相邻顶点的最短距离
for(int j = 1 ; j <= n ; j ++ ){
if(mp[pos][j] != INF && dis[j] > dis[pos] + mp[pos][j]){
dis[j] = dis[pos] + mp[pos][j]; // 找到更近的路径
}
}
}
}
BellManFord
单源最短路算法
时间复杂度为
**缺点:**他会对每一个顶点进行的松弛操作,因此时间消耗巨大。
**优点:**能够处理负数
策略: 按照路径步数来进行遍历,类似于广搜,他会先去遍历第一步能够到达的所有边,以第一步到达的所有边的终点作为松弛的顶点,开始遍历第二步都能到达的所有边,重复一直遍历,每当遍历的时候产生最短路径的数值变化后,继续遍历。
终止条件: 当再一次从头遍历完所有顶点之后,没有任何顶点的最短距离发生变化后,那么才会停止。
PS: 我们可以保证,在次遍历之前,一定可以得到不会发生变化的最短距离数组。
核心思想:枚举所有情况,堪称单源最短路的floyd
这里空空如也
有帮助,赞一个