dijkstra算法详解—简单易懂[通俗易懂]

dijkstra算法详解—简单易懂[通俗易懂]dijkstra算法详解(迪杰斯特拉算法)~~简单易懂,代码附有详细注释,含动态演示图片

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

1 简介

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。这是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止
PS:此算法不能用于求负权图,要求所有边的权重都为非负值。


2 算法思想与原理

dijkstra算法思想是基于贪心算法思想的。所谓贪心算法即始终保持当前迭代解为当前最优解。意思就是在已知的条件下或是当前拥有的全部条件下保证最优解,若在此后的迭代中由于加入了新的条件使得产生了更优解则替代此前的最优解。通过不断的迭代不断保证每次迭代的结果都是当前最优解,那么当迭代到最后一轮时得到的就会是全局最优解。 由于下一轮迭代会参考上一轮的最优解,因此每一轮的迭代的工作量基本一致,降低了整体工作的复杂性。

在最短路径的问题中,局部最优解即当前的最短路径或者说是在当前的已知条件下起点到其余各点的最短距离。关键就在于已知条件,这也是Dijkstra算法最精妙的地方。我们来解释一下。

对于Dijkstra算法,我们假设初始集合(也就是初始条件)不存在任何顶点的,即所有顶点之间是不存在任何路径的,即我们认为所有顶点之间的距离都是无穷大。那么开始加入新的条件,因为我们已知源点距源点距离最小,所以加入进去,并加入它的边,在该条件下,更新该源点到其余顶点的最短距离,选出没有加入到已知集合的距源点距离最小的点,此点最短距离也被确定了(因为其他路径都比这条路径大,无法通过其他路径间接到达这个顶点使得路径更小),然后加入该点与其余还未加入已知条件顶点的边,并以该点迭代刷新最短距离。再重复以上操作,直至所有顶点都加入已知条件集合。


3 具体步骤

  1. 选择起点start与终点end;
  2. 所有点除起点外加入未知集合,并将起点加入已知集合,即至标志位为真,意为已确定该点到源点的最短路径;
  3. 初始化计算,更新起点与其他各点的耗费dis(start,n);
  4. 在未知集合中,选择dis(start,n)中值最小的点x,将x加入已知集合。
  5. 对于剩余顶点中,计算dis(start,n)>dis(start,x)+dis(x,n)
    若真则dis(start,n)=dis(start,x)+dis(x,n),此时start与n点路径经过x点。循环直至goal点加入已知列表,取得dis(start,goal)即为最短距离。

4 动态展示

在这里插入图片描述

5 代码实现(以邻接矩阵为例)

5.1 基本数据

const int inf=0x3f3f3f3f; //代表无穷大。
const int maxn=100;//最大顶点数
int n,m;//n个顶点,m条边。
bool visited[maxn];//判断是否确定到源点的最终最短距离。
int graph[maxn][maxn];//带权图
int dis[maxn];//顶点到源点的最短距离。
int start,goal;//起点与目标点。

Jetbrains全家桶1年46,售后保障稳定

5.2 初始化

void init(){ 
   
	memset(visited,false,sizeof(visited));
	for(int i=1;i<=n;i++){ 
   
		dis[i]=graph[start][i];//初始化dis数组。
	}
}

5.3 dijkstra算法核心

void dijkstra(){ 
   
	//源点为源点start。
	int minn;//记录每趟最短路径中最小的路径值。 
	int pos;//记录得到的minn所对应的下标。
	init();//调用初始化函数。
	visited[start]=true;
	for(int i=1;i<=n;i++){ 
   
		//将n个顶点依次加入判断。
		minn=inf;
		for(int j=1;j<=n;j++){ 
   
			if(!visited[j]&&dis[j]<minn){ 
   
				minn=dis[j];
				pos=j;
			}
		}
		//经过这趟for循环后我们找到的就是我们想要的点,可以确定这点到源点的最终最短距离了。
		visited[pos]=true;//我们将此点并入已知集合。
		//接下来就是更新dis数组了,也就是当前最短距离,这都是针对还没有并入已知集合的点。
		for(int j=1;j<=n;j++){ 
   
			if(!visited[j]&&dis[j]>dis[pos]+graph[pos][j])
				dis[j]=dis[pos]+graph[pos][j];
		}
	}
	//退出循环后,所有的点都已并入已知集合中,得到的dis数组也就是最终最短距离了。
	cout<<dis[goal]<<endl;//输出目标点到源点的最短路径长度。
}

5.4 主函数与头文件等

#include<bits/stdc++.h>

using namespace std;

int main()
{ 
   
    while(cin>>n>>m){ 
   
		memset(graph,inf,sizeof(graph));
		int u,v,w;
		for(int i=0;i<m;i++){ 
   
			cin>>u>>v>>w;
// graph[u][v]=w;//有向图
			graph[u][v]=graph[v][u]=w;//无向图
		}
		cin>>start>>goal;//输入起点与终点。
		dijkstra();
    }
    return 0;
}

6 拓展

如果你学会了dijkstra,那恭喜你成功突破了一关。但是,没有优化的dijkstra算法时间复杂度为 O ( n 2 ) O(n^2) O(n2),如果顶点很多边很少呢等等卡邻接矩阵的题,那么建议你还是要学一下dijkstra的优化版了。详情点击:Dijkstra算法优化~~你一定可以看懂的四种进阶优化

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/203541.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SSD网络原理解析[通俗易懂]

    SSD网络原理解析[通俗易懂]SSD网络是继YOLO之后的one-stage目标检测网络,是为了改善YOLO网络设置的anchor设计的太过于粗糙而提出的,其设计思想主要是多尺度多长宽比的密集锚点设计和特征金字塔,下面我将详细的解析SSD网络结构SSD网络结构精简版详细版通过上面这个图,大家可以清楚的看到SSD的网络结构主要分为以下几个部分:VGG16BaseLayer ExtraFeatureLayer DetectionLayer NMS补充说明:在整个SSD网络中,其…

    2022年10月23日
  • SQL SERVER插件之SQLPrompt 激活使用

    SQL SERVER插件之SQLPrompt 激活使用如有不懂,可以关注麒琳技术栈,欢迎在线咨询

  • 选择排序(C语言实现)

    选择排序(C语言实现)选择排序(C语言实现)实现原理:给出一组数据,第1轮在待排序记录r[1]-r[n]中选出最小的记录,将它与r[1]交换;第2轮在待排序记录r[2]-r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。代码初始序列:{49276597761238}第1趟:12与49交换:12{276597764938}第2趟:27不动:1227{6597764938}

  • python解释器找不到_python解释器路径

    python解释器找不到_python解释器路径Pycharm“nothingtoshow”ininterpreters(解决Pycharm无法找到编译器的问题)问题描述解决方案问题原因解决过程问题描述暑假放假两周,两周没写代码,打开PyCharm发现编译器找不到了(PythonInterpreterNothingtoshow),程序自然也无法运行,如图:解决方案解决方案来自StackOverflow,原出处:link.(https://stackoverflow.com/questions/67297284/pycharm

  • scikit-learn : LARS[通俗易懂]

    scikit-learn : LARS[通俗易懂]LARS正则化斯坦福大学的BradleyEfron,TrevorHastie,IainJohnstone和RobertTibshirani发现了LARS(LeastAngleRegression,最小角回归)它借用了威廉·吉尔伯特·斯特朗(WilliamGilbertStrang)介绍过的高斯消元法(Gaussianelimination)的灵感。背景LARS是一种回归手段,适

  • Java生成MD5的两种方式

    Java生成MD5的两种方式1原生的packagecom.pibigstar.common.utils;importjava.security.MessageDigest;/***MD5加密工具类*@authorpibigstar**/publicclassMyMD5Util{//盐,用于混交md5privatestaticfinalStringsl…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号