最短路径之Dijkstra算法

简介: 最短路径之Dijkstra算法

Dijkstra算法有些类似于最小生成树中prim算法,从源点出发,每次选出一个最短路径,然后依次更新n次。

下面是代码实现


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxv=101;
const int inf=10000000;
struct node{
  int v,weight;
};
vector<node>Adj[maxv] ;
bool vis[101];//标记 
int dis[101];//记录最短距离 
int pre[101];//记录路径 
//dijkstra算法
void dijkstra (int n) {
  fill(vis,vis+n,false);
  fill(dis,dis+n,inf); //初始化dis和vis
  for(int i=0;i<n;i++) 
  pre[i]=i;  //路径初始化 
  dis[0] =0;//这里求零点到各点最短距离
  for(int i=0;i<n;i++) //循环n次
  {    
      int min=inf,u=-1;
    for(int j=0;j<n;j++) 
     //找最短距离点 ,这里可以用优先队列存储dis下标更快 
    {
      if(!vis[j]&&dis[j]<min)
      {
        u=j;
        min=dis[j];
      }
    }
    if(u==-1) return ;//没有找到 
    vis[u] =true;//标记已经找到的u 
    for(int j=0;j<Adj[u].size();j++) //更新dis 
    {
      int x=Adj[u][j].v;
      if(!vis[x]&&dis[u]+Adj[u][j].weight<dis[x])
      {dis[x]=dis[u]+Adj[u][j].weight;
      pre[x]=u;//到达x的前一个端点是u 
    }
  //遇到一些问题此处可以加第二条件,比如边权、点权、多少条最短路径等 
  } 
} 
}
 void dfs(int s,int n){//输出路径 
  if(pre[n]==s)
  {
    printf("%d ",s);
    return;
   }
  dfs(s,pre[n]);
  printf("%d ",n);
 }
int main(){
  return 0;
}

实际上,上面的程序只储存了一条路径,如果可能有多条路径并要求都打印出来怎么办?

这时将pre变成vector<int>型自然就可以存放多条路径,然后在dfs里面递归输出即可。

那么问题又来了,如果两条路径相同时,叫你选择出花费最少、字典序最小、点权和最大等一些条件怎么办?

有两个思路:

1.前面提到dfs里面可以输出多条路径,不如在遍历这些路径的时候,记录下符号其他条件的路径,保持更新即可,这是Dijkstra+dfs算法的解决思路。

2.也可以直接在执行Dijkstra过程中解决,其有一个更新dis的操作,在更新这个操作的时候我们可以同时也更新花费、点权和等其他条件

前者具有通用性,特别是一定要输出路径时,推荐使用前者,如果只是要一个值,后者比较简洁,下面两种方法的应用:

Dijkstra+Dfs+邻接表:

https://blog.csdn.net/qq_36684096/article/details/104728599


Dijkstra+邻接矩阵+第二指标:

https://blog.csdn.net/qq_36684096/article/details/104728264


相关文章
|
4月前
|
存储 运维 监控
基于 C# 语言的 Dijkstra 算法在局域网内监控软件件中的优化与实现研究
本文针对局域网监控系统中传统Dijkstra算法的性能瓶颈,提出了一种基于优先队列和邻接表优化的改进方案。通过重构数据结构与计算流程,将时间复杂度从O(V²)降至O((V+E)logV),显著提升大规模网络环境下的计算效率与资源利用率。实验表明,优化后算法在包含1000节点、5000链路的网络中,计算时间缩短37.2%,内存占用减少21.5%。该算法适用于网络拓扑发现、异常流量检测、故障定位及负载均衡优化等场景,为智能化局域网监控提供了有效支持。
90 5
|
14天前
|
机器学习/深度学习 编解码 算法
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
【机器人路径规划】基于迪杰斯特拉算法(Dijkstra)的机器人路径规划(Python代码实现)
104 4
|
2月前
|
算法 机器人 定位技术
基于机器视觉和Dijkstra算法的平面建筑群地图路线规划matlab仿真
本程序基于机器视觉与Dijkstra算法,实现平面建筑群地图的路径规划。通过MATLAB 2022A读取地图图像,识别障碍物并进行路径搜索,支持鼠标选择起点与终点,最终显示最优路径及长度,适用于智能导航与机器人路径规划场景。
|
12月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
627 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
8月前
|
存储 算法 测试技术
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
|
8月前
|
算法 编译器 C++
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)
|
8天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
9天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
11天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
85 11
|
11天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)

热门文章

最新文章