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)
blank

相关推荐

  • 开启Scrapy爬虫之路

    开启Scrapy爬虫之路七夜大佬的《python爬虫开发与项目实战》,买了好多年了,学习了好多东西,基本上爬虫都是在这里面学的,后期的scrapy框架爬虫一直不得门而入,前段时间补了下面向对象的知识,今天突然顿悟了!写个笔记记录下学习过程

  • 网站管理后台帐号密码暴力激活成功教程方法

    网站管理后台帐号密码暴力激活成功教程方法【导读】对于网站运行的个人站长而言,最担心的是应如何有效且安全的去管理自己的网站,否则自己辛辛苦苦经营的网站就会被不请自来的不速之客给攻破,轻则站点数据被窃取,重则整个网站都被攻陷,导致无法恢复。本文主要从管理后台这个方面来讲解其黑客攻击过程,并通过在虚拟环境中展开实例演示,各读者可以跟着本教程去做实验,通过实验加强对攻击过程的了解,如果你是一名菜鸟站长也可以针对性的去做一下防护方案。…

  • win10下nessus家庭版安装和简单使用「建议收藏」

    win10下nessus家庭版安装和简单使用「建议收藏」1.访问nessue官网下载:https://www.tenable.com/downloads/nessus?loginAttempted=true2.没有找到windows64位,这里下载了windows服务器版64位的3.双击下载的安装包进行安装,一直Next即可4.浏览器访问:http://localhost:8834即可打开Nessus(用谷歌可以直译成中文),如打开浏览器报错选择高级\进阶继续访问就行,点击‘ConnectviaSSL’5.

  • mongodb 学习笔记 04 — 游标、索引「建议收藏」

    mongodb 学习笔记 04 — 游标、索引

  • Linux 搭建 Kafka教程[通俗易懂]

    Linux 搭建 Kafka教程[通俗易懂]把kafka解压到linux去配置文件中配置环境配置kafka文件内容进入kafka/config目录修改server.properties文件修改broker.id=id里面的数值不可以重复同时添加主机的ip和端口host.name=192.168.10.101listeners=PLAINTEXT://192.168.10.101:9092在下面找到log.dirs修改日志的地址修改为我们三台机器ip地址zookeeper.connect=localhost:21

    2022年10月16日
  • 不要再走弯路了,最全的黑客入门学习路线在这[通俗易懂]

    不要再走弯路了,最全的黑客入门学习路线在这[通俗易懂]在大多数的思维里总觉得学习网络安全得先收集资料、学习编程、学习计算机基础,这样不是不可以,但是这样学效率太低了!你要知道网络安全是一门技术,任何技术的学习一定是以实践为主的。也就是说很多的理论知识其实是可以在实践中去验证拓展的,这样学习比起你啃原理、啃书本要好理解很多。所以想要学习网络安全选对正确的学习方法很重要,这可以帮你少走很多弯路。因为如果你选择了一个低效的方法,也许别人都已经彻底学会了,你还停留在入门阶段。对于小白来说,有个人引导会比自学要高效的多,尤其是容易坚持不下去的小伙伴。学姐

发表回复

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

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