最短路之Dijkstra算法

简介: 最短路之Dijkstra算法

单源最短路径Dijkstra

关于原理

看文—看图

注意

注意Dijkstra不能处理存在负边权的题目

由于“估计值”5<6,所以3先确定了,3确定了之后再确定的2,所以1->3的距离不会变


以A为源,线路是单向的,也就是说A->B最小就是4,不会等于2的


模板

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define INF 0x3f3f3f3f
using namespace std;
int map[1005][1005];
int dis[1005],book[1005];
int main() {
  int n,m;
  while(cin>>m>>n) {
    memset(dis,0,sizeof(dis));
    memset(book,0,sizeof(book));
    memset(map,INF,sizeof(map));
    for(int i=1; i<=n; i++)
      map[i][i]=0;//自己到自己为0,其他初始化为正无穷
    for(int i=1; i<=m; i++) {
      int x,y,z;
      cin>>x>>y>>z;
      map[x][y]=z;
    }
    for(int i=1; i<=n; i++)
      dis[i]=map[1][i];//以1为源,存储1到别的点的“估计值”
    book[1]=1;//点1是确定值
    for(int i=1; i<=n-1; i++) {
      int min=INF;
      int u=1;
      for(int j=1; j<=n; j++) {
        if(book[j]==0 && dis[j]<min) {
          min=dis[j];
          u=j;//在估计值中选取权最小的
        }
      }
      book[u]=1;//把1到别的点的“估计值”的权最小的点变成确定值
      for(int j=1; j<=n; j++) {
        if(map[u][j]<INF ) {//找到与u相连的点,设为x
          if(dis[j]>dis[u]+map[u][j] && book[j]==0 )//更新估计值,确定值不变
            dis[j]=dis[u]+map[u][j];//1->u,u->x的线路比1->x的线路优,所以更新1->x的线路
        }
      }
    }
    cout<<dis[n]<<endl;//dis[n]即1->x的最短路
  }
}



目录
相关文章
|
7天前
|
人工智能 算法 数据可视化
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2
434 0
|
7天前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-5 算法训练 最短路
26 0
|
7天前
|
存储 人工智能 算法
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1
112 0
|
7天前
|
算法
讲课:拓扑排序、最短路算法
讲课:拓扑排序、最短路算法
|
7天前
|
网络协议 算法 数据库
【专栏】IS-IS协议是内部网关协议,常用于大型网络路由器间的路由信息交换,基于OSI的CLNP标准和Dijkstra算法
【4月更文挑战第28天】IS-IS协议是内部网关协议,常用于大型网络路由器间的路由信息交换,基于OSI的CLNP标准和Dijkstra算法。其特点是分层设计、快速收敛、高效资源利用和强故障恢复能力。在现代网络中,IS-IS广泛应用于服务提供商、企业网络及与其他协议的融合,是构建稳定、高效网络的关键。了解和应用IS-IS能提升网络系统的可靠性和效率。
|
7天前
|
人工智能 算法 BI
D - Silver Cow Party——POJ3268(连续用两次Dijkstra算法)
D - Silver Cow Party——POJ3268(连续用两次Dijkstra算法)
|
7天前
|
算法
Heavy Transportation(Dijkstra算法)
Heavy Transportation(Dijkstra算法)
|
7天前
|
算法
关于Dijkstra算法
关于Dijkstra算法
|
7天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
4天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
24 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长