最短路之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的最短路
  }
}



目录
相关文章
|
存储 运维 监控
基于 C# 语言的 Dijkstra 算法在局域网内监控软件件中的优化与实现研究
本文针对局域网监控系统中传统Dijkstra算法的性能瓶颈,提出了一种基于优先队列和邻接表优化的改进方案。通过重构数据结构与计算流程,将时间复杂度从O(V²)降至O((V+E)logV),显著提升大规模网络环境下的计算效率与资源利用率。实验表明,优化后算法在包含1000节点、5000链路的网络中,计算时间缩短37.2%,内存占用减少21.5%。该算法适用于网络拓扑发现、异常流量检测、故障定位及负载均衡优化等场景,为智能化局域网监控提供了有效支持。
425 5
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
1533 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
机器学习/深度学习 编解码 算法
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
877 4
|
算法 机器人 定位技术
基于机器视觉和Dijkstra算法的平面建筑群地图路线规划matlab仿真
本程序基于机器视觉与Dijkstra算法,实现平面建筑群地图的路径规划。通过MATLAB 2022A读取地图图像,识别障碍物并进行路径搜索,支持鼠标选择起点与终点,最终显示最优路径及长度,适用于智能导航与机器人路径规划场景。
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
1059 0
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
623 2
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
548 3

热门文章

最新文章