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


目录
打赏
0
0
0
0
1
分享
相关文章
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
126 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
路径规划算法 - 求解最短路径 - A*(A-Star)算法
路径规划算法 - 求解最短路径 - A*(A-Star)算法
219 1
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
83 0
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
|
6月前
|
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
142 0
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
基于遗传优化算法的风力机位置布局matlab仿真
本项目基于遗传优化算法(GA)进行风力机位置布局的MATLAB仿真,旨在最大化风场发电效率。使用MATLAB2022A版本运行,核心代码通过迭代选择、交叉、变异等操作优化风力机布局。输出包括优化收敛曲线和最佳布局图。遗传算法模拟生物进化机制,通过初始化、选择、交叉、变异和精英保留等步骤,在复杂约束条件下找到最优布局方案,提升风场整体能源产出效率。
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
149 68

热门文章

最新文章