最短路径——迪杰斯特拉算法

简介: 版权声明:本文为博主原创文章,转载请注明出处http://blog.csdn.net/u013132758。 https://blog.csdn.net/u013132758/article/details/52293788 前言好久没有更新过算法的博客了,这篇博客主要介绍我们算法中很著名的一个问题——最短路径问题及解决最短路径问题的经典算法之一迪杰斯特拉算法。
版权声明:本文为博主原创文章,转载请注明出处http://blog.csdn.net/u013132758。 https://blog.csdn.net/u013132758/article/details/52293788

前言

好久没有更新过算法的博客了,这篇博客主要介绍我们算法中很著名的一个问题——最短路径问题及解决最短路径问题的经典算法之一迪杰斯特拉算法。

最短路径问题

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。算法具体的形式包括:                         

  • 确定起点的最短路径问题 -即已知起始结点,求最短路径的问题。
  • 确定终点的最短路径问题 -与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题。在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
  • 确定起点终点的最短路径问题 -即已知起点和终点,求两结点之间的最短路径。
  • 全局最短路径问题 -求图中所有的最短路径。
其实就是字面意思,一个带边值的图中从某一个顶点到另外一个顶点的最短路径。如下图所示:你能求出V0-V8的最短路径吗?

而解决最短路径问题最常见的算法就是迪杰斯特拉(Dijkstra)算法和弗洛伊德算法(Floyd)算法。

迪杰斯特拉(Dijkstra)算法

1.算法简介

Dijkstra算法是由E.W.Dijkstra于1959年提出,又叫迪杰斯特拉算法,它应用了贪心算法模式,是目前公认的最好的求解最短路径的方法。算法解决的是有向图中单个源点到其他顶点的最短路径问题,其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点。但由于dijkstra算法主要计算从源点到其他所有点的最短路径,所以算法的效率较低。

2.算法原理

1.首先,引入一个辅助向量D,它的每个分量 D
 [i]
表示当前所找到的从起始点
 v
(即源点
 v 
)到其它每个顶点
 vi
的长度。
例如,D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。
2.D的初始状态为:若从v 到vi   有弧(即从v  vi   存在连接边),则D[i]   为弧上的权值(即为从  v   到vi   的边的权值);否则置D[i]   为∞。 显然,长度为 D  [j]   = Min{ D |  vj   ∈V } 的路径就是从v   出发到顶点vj   的长度最短的一条路径,此路径为(v,vj   )。
3.那么,下一条长度次短的是哪一条呢?也就是找到从源点v 到下一个顶点的最短路径长度所对应的顶点,且这条最短路径长度仅次于从源点v   到顶点  vj   的最短路径长度。 假设该次短路径的终点是vk ,则可想而知,这条路径要么是(  v,vk   ),或者是(v,vj,vk   )。它的长度或者是从v 到vk   的弧上的权值,或者是D  [j]   加上从vj   到vk   的弧上的权值。
4.一般情况下,假设S为已求得的从源点v 出发的最短路径长度的顶点的集合,则可证明:下一条次最短路径(设其终点为x )要么是弧(v,x   ),或者是从源点     出发的中间只经过S中的顶点而最后到达顶点     的路径。 因此,下一条长度次短的的最短路径长度必是D[j] = Min{ D[i]   |vi   ∈V-S },其中D  [i]   要么是弧(  v,vi   )上的权值,或者是D  [k]   (  vk   ∈S)和弧(  vk   ,  vi   )上的权值之和。

3、算法实例

我们看下面这幅图 求从 a 到 j 的最短路径。

4、算法实现

#include<stdio.h>
#include<stdlib.h>
#define max 11000000000
inta[1000][1000];
intd[1000];//d表示某特定边距离
intp[1000];//p表示永久边距离
inti,j,k;
intm;//m代表边数
intn;//n代表点数
intmain()
{
scanf("%d%d",&n,&m);
intmin1;
intx,y,z;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
a[x][y]=z;
a[y][x]=z;
}
for(i=1;i<=n;i++)
d[i]=max1;
d[1]=0;
for(i=1;i<=n;i++)
{
min1=max1;
for(j=1;j<=n;j++)
if(!p[j]&&d[j]<min1)
{
min1=d[j];
k=j;
}
p[k]=j;
for(j=1;j<=n;j++)
if(a[k][j]!=0&&!p[j]&&d[j]>d[k]+a[k][j])
d[j]=d[k]+a[k][j];
}
for(i=1;i<n;i++)
printf("%d->",p[i]);
printf("%d\n",p[n]);
return0;
}

5、性能分析

迪杰斯特拉算法的时间复杂度为O(n^2),空间复杂度为O(n^3)。正因为如此当图中点较多时,算法的效率会很低。于是就有了对迪杰斯特拉算法的优化,最常见的就是堆优化,后期将为大家介绍迪杰斯特拉算法的优化。

相关文章
|
3月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
110 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
3月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
5月前
|
算法 定位技术
路径规划算法 - 求解最短路径 - A*(A-Star)算法
路径规划算法 - 求解最短路径 - A*(A-Star)算法
184 1
|
5月前
|
自然语言处理 算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
72 0
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
|
6月前
|
算法 Java
Java语言实现最短路径算法(Shortest Path)
Java语言实现最短路径算法(Shortest Path)
78 3
|
5月前
|
算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
126 0
|
8天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。
|
21天前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
156 80
|
9天前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
|
9天前
|
算法
基于龙格库塔算法的锅炉单相受热管建模与matlab数值仿真
本设计基于龙格库塔算法对锅炉单相受热管进行建模与MATLAB数值仿真,简化为喷水减温器和末级过热器组合,考虑均匀传热及静态烟气处理。使用MATLAB2022A版本运行,展示自编与内置四阶龙格库塔法的精度对比及误差分析。模型涉及热传递和流体动力学原理,适用于优化锅炉效率。