程序员经验分享-hwhale

数据结构——迪杰斯特拉（Dijkstra）算法

2023-10-26

迪杰斯特拉算法又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
以下是数据结构中关于迪杰斯特拉算法的操作（编程风格参考严蔚敏版数据结构）。

头文件及宏定义

#include<iostream>
#include<stdio.h>
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100
#define ArcNum 100
#define OK 1
#define ERROR -1
#define NOTPRENODE -1
typedef int status;

说明： NOTPRENODE表示无前驱结点

图以及辅助数组的声明

bool S[MVNum];
int Path[MVNum];
int D[MVNum];
typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 8;
}AMGraph;

说明：
S[MVNum];//记录源点到终点vi的是否已被确定的最短路径长度，true表示确定false表示未确定（换个说法就是：源点到vi的边如果被选中并确定就是true，如果只是被选中并没将vi确定下来则是false）。
…
Path[MVNum];//记录源点到终点vi当前最短路径上vi的直接前驱顶点序号（如果没有前驱则为-1）。比如A（下标为0）、C（下标为2），如果将当前最短路径边选为AC（注意，只是暂选AC而不一定是确定AC，此时Path会更新而S不一定会更新），那么Path[2] = 0。
…
D[MVNum];//记录从源点到终点vi的当前最短路径长度（如果没有弧则为无穷大），其实说白了D就是一个路径权值表。 这个D的值一定要记住，是从源点开始到vi的值！是从源点开始！是从源点开始！例如，AC权值为10，CD（D下标为3）权值为20。假设过程中选择了A到D的最短路径是A->C->D，那么D[3] = 10+20=30。千万别写成那么D[3] = 20，这是错的！

举个例子：

在这里插入图片描述

构建有向图

status CreateSDG(AMGraph &G){//创建有向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = NOTPRENODE;
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][2]=10;G.arcs[0][4]=30;G.arcs[0][5]=100;
	G.arcs[1][2]=5;
	G.arcs[2][3]=50;
	G.arcs[3][5]=10;
	G.arcs[4][3]=20;G.arcs[4][5]=60;
	return OK; 
}

注意！有向图的邻接矩阵不一定对称（当有向图的邻接矩阵对称就是其特殊情况无向图）
老样子先生成邻接矩阵：
在这里插入图片描述

初始化三个辅助数组（S、Path、D）：

void initial(AMGraph &G,VerTexType v0){
	int v0i = LocateVex(G,v0);//(v0-index,源点v0的下标)
	for(int vi=0;vi<G.vexnum;vi++){
		S[vi] = false;//S初始状态为空集 
		D[vi] = G.arcs[v0i][vi];//将v0到各个终点的最短路径初始化弧上的权值（其实就是先把v0和其它点先强行直连起来） 
		if(D[vi]<MaxInt&&D[vi]!=0){
			Path[vi] = v0i;//如果v0和vi之间有弧，将vi的前置节点设为v0。 
		} else{
			Path[vi] = NOTPRENODE;
		} 
	} //for
	S[v0i] = true;//将v0加入S；
	D[v0i] = 0;//源点到源点自身的距离为0 
}

第一步：S全置false（全部未选）
第二步：把源点和其它点的边录入D中（没有边的以无穷大的形式录入）
第三步：如果源点可以到某个节点，那么该节点的先驱节点设置成源点；否则设置为无前驱节点
第四步：将源点的S置true（表示源点已被选择），源点到源点自己的距离D设为0。

迪杰斯特拉（Dijkstra）核心算法

void Dijkstra(AMGraph &G,VerTexType v0){
	int v0i = LocateVex(G,v0);
	//每次求得v0到某个顶点v的最短路径，将v加到S集 
	for(int i=1;i<G.vexnum;i++){//对其余的n-1个点进行计算 
		int min = MaxInt;
		int t;//中间变量 
		for(int j=0;j<G.vexnum;j++){
			if(!S[j]&&D[j]<min){//选出一条最短的路径，终点为j 
				t = j;//记录节点j 
				min = D[j];//当前最短路径权值是D[j] 
			}//if
		} //for
		S[t] = true;//终点t已被选择 
		for(int j=0;j<G.vexnum;j++){//更新从v0出发到其它点集合上所有最短路径长度 
			if(!S[j]&&(D[t]+G.arcs[t][j]<D[j])){//如果源点经过t点到j的距离小于源点直接到j点的距离。
				D[j] = D[t]+G.arcs[t][j];//更新D 
				Path[j] = t;//更改前驱为t。 
			}
		} 
	}//for
}

第一步：作n-1重循环（对除源点以外的节点进行遍历）
第二步：在当前路径权值表D中选出权值最短的边，记录该边的终点vi，并将该点vi的S设为已选择
第三步：将源点直接到剩下未被选择的节点vj的距离与源点经过vi节点再到未被选择的节点vj的距离进行比较（此时vi充当一个中间节点的作用），如果源点直接到vj的距离短则不作操作（初始化的时候已经操作完毕了），如果源点经过vi到达vj的距离更短，则将D[j]的距离修改为源点到vi的距离加上vi到vj的距离，那么vj点的前驱就从源点变成了vi（因为源点要经过vi到vj了）。重复第二第三步，直到选出源点分别到全部节点的最短路径（D的最后数据就是最短路径结果）。

用上例图进行手推运行过程（天蓝色表示S，绿色表示选出边但未确认终点，深蓝色表示选出边且确认终点，紫色表示该节点的前驱节点）：

1、三个辅助数组的初始化：
在这里插入图片描述
2、第一次大循环：AC权值最小，选择AC。C设置为已选择。
进行小循环：ACB的权值不小于AB，不进行操作；AD的权值小于ACD（下标为3）的权值，修改D【3】=AC+CD = 10+50 = 60，D的前驱结点修改为C。注意：D【3】表示为AD距离为60了。AE的权值30小于ACD权值，不进行操作；AF权值100小于ACF权值，不进行操作。
在这里插入图片描述
3、第二次大循环：AE权值30最短，选择AE（下标4），将E标记为已选择。
进行小循环：AEB权值不小于AB，不作操作；AED权值30+20=50小于AD权值（D下标为3），修改D【3】=50（意思是AD距离为50），D的前驱结点修改为E；AEF权值30+60=90小于AF（下标5）的权值100，修改D【5】=90（意思是AF距离为50），F前驱节点修改为为E；
在这里插入图片描述
4、第三次大循环：选出AED权值50最小，选出AD，D标记为已选择。
进行小循环：ADB权值不小于AB，不进行操作；ADF权值50+10=60小于AF的权值90，D【5】=60（意思是AF距离为60），将F的前驱结点设置成E；
在这里插入图片描述
5、第四次大循环：选出最短边AF权值60，将F标记已被选择。
进行小循环：AFB的权值不小于AB的权值，不作操作。
在这里插入图片描述
第五次大循环：未选择的边只有AB边了，但是由于AB的没有变（距离为无穷大），B不能被选择。
因为全部节点都被已被选择，小循环不作任何操作。程序结束（所以B的前驱结点一直都是NOTPRENODE）。
在这里插入图片描述

运行结果

在这里插入图片描述

源代码

#include<iostream>
#include<stdio.h>
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100
#define ArcNum 100
#define OK 1
#define ERROR -1
#define NOTPRENODE -1
typedef int status;
bool S[MVNum];//记录源点到终点vi的是否已被确定的最短路径长度，true表示确定false表示未确定 
int Path[MVNum];//记录源点到终点vi当前最短路径上vi的直接前驱顶点序号（如果没有前驱则为-1）
int D[MVNum];//记录从源点到终点vi的当前最短路径长度（如果没有弧则为无穷大）。 
typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 8;
}AMGraph; 

status CreateSDG(AMGraph &G){//创建有向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = NOTPRENODE;
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][2]=10;G.arcs[0][4]=30;G.arcs[0][5]=100;
	G.arcs[1][2]=5;
	G.arcs[2][3]=50;
	G.arcs[3][5]=10;
	G.arcs[4][3]=20;G.arcs[4][5]=60;
	return OK; 
}

void ShowGraph(AMGraph G){
	cout<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<" "<<G.vexs[i];
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]==MaxInt||G.arcs[i][j]==NOTPRENODE){
				cout<<"* ";
			}else{
				cout<<G.arcs[i][j]<<" ";
			}
		}
		cout<<endl;
	}
}

int LocateVex(AMGraph G, VerTexType v){
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v){
			return i;
		}
	} 
	return ERROR;
}

void initial(AMGraph &G,VerTexType v0){
	int v0i = LocateVex(G,v0);//(v0-index,源点v0的下标)
	for(int vi=0;vi<G.vexnum;vi++){
		S[vi] = false;//S初始状态为空集 
		D[vi] = G.arcs[v0i][vi];//将v0到各个终点的最短路径初始化弧上的权值（其实就是先把v0和其它点先强行直连起来） 
		if(D[vi]<MaxInt&&D[vi]!=0){
			Path[vi] = v0i;//如果v0和vi之间有弧，将vi的前置节点设为v0。 
		} else{
			Path[vi] = NOTPRENODE;
		} 
	} //for
	S[v0i] = true;//将v0加入S；
	D[v0i] = 0;//源点到源点自身的距离为0 
}

void Dijkstra(AMGraph &G,VerTexType v0){
	int v0i = LocateVex(G,v0);
	//每次求得v0到某个顶点v的最短路径，将v加到S集 
	for(int i=1;i<G.vexnum;i++){//对其余的n-1个点进行计算 
		int min = MaxInt;
		int t;//中间变量 
		for(int j=0;j<G.vexnum;j++){
			if(!S[j]&&D[j]<min){//选出一条最短的路径，终点为j 
				t = j;//记录节点j 
				min = D[j];//当前最短路径权值是D[j] 
			}//if
		} //for
		S[t] = true;//终点t已被选择 
		for(int j=0;j<G.vexnum;j++){//更新从v0出发到其它点集合上所有最短路径长度 
			if(!S[j]&&(D[t]+G.arcs[t][j]<D[j])){//如果源点经过t点到j的距离小于源点直接到j点的距离。 
				D[j] = D[t]+G.arcs[t][j];//更新D 
				Path[j] = t;//更改前驱为t。 
			}
		} 
	}//for
}

void show(){
	cout<<"S:";
	for(int i=0;i<6;i++){
		if(S[i]){
			cout<<"T ";
		}else{
			cout<<"F ";
		}
	}
	cout<<endl;
	cout<<"D:";
	for(int i=0;i<6;i++){
		if(D[i]==MaxInt){
			cout<<"*"<<" ";
			continue;
		}
		cout<<D[i]<<" ";
	}
	cout<<endl;
	cout<<"P:";
	for(int i=0;i<6;i++){
		cout<<Path[i]<<" ";
	}
	cout<<endl; 
} 


int main(){
	AMGraph G;
	CreateSDG(G);
	initial(G,'A'); 
	cout<<"辅助数组初始化:\n";
	show();
	cout<<endl;
	Dijkstra(G,'A');
	ShowGraph(G);
	cout<<endl;
	cout<<"程序结束的辅助数组:\n";
	show();
	return 0;
}

时间复杂度与空间复杂度

时间复杂度: 迪杰斯特拉算法的时间复杂度为 O(n×n),其中 n 表示节点个数,当图 中节点越多时,迪杰斯特拉算法花费的时间就越多。

空间复杂度: 迪杰斯特拉算法的空间复杂度也是 O(n×n),其中 n 表示节点个数,当 图中节点越多时,迪杰斯特拉算法的空间复杂度也就越大。

敬请批评指正！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

算法

图论

Dijkstra

最短路径

数据结构——迪杰斯特拉（Dijkstra）算法 的相关文章

随机推荐

  • W800系列

    目录 续前文 调试前配置 下载调试 增加一个新的demo 目前存在的问题 待解决 win11系统提示调试错误 驱动问题解决步骤 供复现及参考分析用 调试仿真错误 T HeadDebugServer运行截图 续前文 W800系列 ST LIN

  • 用例的一些知识

    一 用例执行 说明 执行结果与用例的期望结果不一致 含义 为缺陷 提示 用例结果不通过为缺陷 需要进行缺陷管理 二 缺陷 01定义 软件中存在的各种问题 都为缺陷 简称bug 02缺陷标准 少功能 功能错误 多功能 缺少隐形功能 易用性 软

  • Android NDK 开发：实战案例

    0 前言 如果只学理论 不做实践 不踩踩坑 一般很难发现真正实践项目中的问题的 也比较难以加深对技术的理解 所以延续上篇 JNI 的实战Android NDK开发 JNI实战篇 这篇主要是一些 NDK 小项目的练习 由于这些项目网上都有 d

  • CGAL---点云处理

    CGAL是一款几何处理库 但是介绍其在点云中处理的资料比较少 现介绍一个专门介绍CGAL在点云数据中处理的网站 比包括常见的点云数据处理 功能包括 1 聚类 欧式聚类 2 配准 ICP 3 简化 格网 4 平滑 5 法向量估算 6 特征估算

  • C++ static的作用

    1 什么是static static 是C 中很常用的修饰符 它被用来控制变量的存储方式和可见性 2 为什么要引入static 函数内部定义的变量 在程序执行到它的定义处时 编译器为它在栈上分配空间 大家知道 函数在栈上分配的空间在此函数执

  • 鱼眼去锯齿

    include

  • hexo更换主题后出现问题：WARN No layout: index.html

    hexo更换主题后出现问题 WARN No layout index html hexo本地测试运行重启后页面空白 hexo g出现以上错误 错误原因 运行git clone 指令获得主题后 假设是NEXT主题 在theme主题下保存文件夹

  • 火狐不能同步的问题

    火狐不能同步的问题 解决方法 下载同版本的软件并且切换成同一个服务器类型 打开 帮助 gt 关于Firefox 查看连个软件版本号和上线时间是否一致 如果不一致 则下载最新版 同版本同上线时间 的软件 如果一致 右上角菜单 gt 选项 gt

  • 【状态估计】基于UKF法、AUKF法的电力系统三相状态估计研究（Matlab代码实现）

    欢迎来到本博客 博主优势 博客内容尽量做到思维缜密 逻辑清晰 为了方便读者 座右铭 行百里者 半于九十 本文目录如下 目录 1 概述 2 运行结果 3 参考文献 4 Matlab代码及数据 1 概述 基于UKF法和AUKF法的电力系统三相状

  • Unity 鼠标拖动旋转物体，并且物体不会越转越乱

    用Mathf Abs 绝对值 计算鼠标水平和竖直方向谁的位移更大 减少因为一丢丢的其他方向移动导致的物体微幅旋转影响后面物体旋转会越来越混乱 这样可以让物体旋转更好的单个方向进行旋转 代码如下 public float speed 2f v

  • vue使用富文本编辑器:vue-quill-editor粘贴图片+图片上传服务器+预览图片

    引入vue quill editor 初始化vue quill editor npm install vue quill editor save 部分页面引入组件 import quill dist quill core css impor

  • 51单片机实现串口通信（主单片机到从单片机发送LED流水灯）

    其实这是个51单片机串口通信的小例子 课堂上老师说你们可以去尝试弄一下 于是就去网上找一下资料 就做了这个实验 先把一个作为主机 用来发送数据 另一个作为从机 用来接收数据 将两个程序各自烧录到对应的板子上去 并将主机的TX P3 0 接到

  • VS C++ 生成类图

    C 中如何快速清晰的了解定义类型及类型之间的关联关系 一个好的类图有助于你快速了解 那么怎么去生成一个类图呢 下面步骤可以帮到你 一 安装类设计器组件 1 确定是否已经安装 类设计器 如果未安装 可以打开 工具 gt 获取工具和功能 或者直

  • springboot Junit单元测试默认事务不提交

    目录 一 Junit初次使用 二 Junit事务问题 1 默认不提交事务 默认回滚 2 设置rollback 让Junit提交事务 一 Junit初次使用 因为以前总觉得Junit单元测试配置比较繁琐 代码功能大多使用main方法或者pos

  • SD秋叶安装教程

    前言 本部署整合包基于开源项目 stable diffusion webui制作 部署包作者 秋葉aaaki 免责声明 本安装包及启动器免费提供 无任何盈利目的 电脑配置要求 操作系统 windows10以后 CPU 不做强制要求 内存 推

  • 输出斐波那契数列的每一项，每五个换行

    7 2 利用数组计算斐波那契数列 15 分 本题要求编写程序 利用数组计算菲波那契 Fibonacci 数列的前N项 每行输出5个 题目保证计算结果在长整型范围内 Fibonacci数列就是满足任一项数字是前两项的和 最开始两项均定义为1

  • FFmpeg录制流

    FFmpeg下windows安装 下载地址 http ffmpeg org download html windows 下载 ffmpeg release essentials zip 这个文件名 解压后将bin目录加到环境变量path 录

  • 内存使用(分段、分区、分页、多级页表、快表)--OS

    内存使用 内存使用 将程序放在内存中 PC指向内存地址 首先 我们需要让程序进入内存 举个例子 int main int argc char argv text entry 入口地址 call main call exit main ret

  • windows默认文件(桌面、下载、文档等)设置为C盘根路径后怎么修改回去

    桌面 下载 文档等设置为C盘根路径后怎么修改回去 1 问题 2 解决办法 2 1 按 Win R 调出运行窗口 输入 regedit 并按回车 2 2 在弹出的注册表窗口里 打开下面路径 计算机 HKEY CURRENT USER SOFT

  • 数据结构——迪杰斯特拉（Dijkstra）算法

    迪杰斯特拉算法又叫狄克斯特拉算法 是从一个顶点到其余各顶点的最短路径算法 解决的是有权图中最短路径问题 迪杰斯特拉算法主要特点是从起始点开始 采用贪心算法的策略 每次遍历到始点距离最近且未访问过的顶点的邻接节点 直到扩展到终点为止 以下是数

热门标签