《数据结构与算法》——Dijkstra算法总结

矫情吗；* 2021-12-07 10:29 273阅读 0赞

# 《数据结构与算法》——Dijkstra算法总结 #

在考研中，图的应用部分有四个大考点分别为**最小生成树**、**最短路径问题**、**拓扑排序**以及**关键路径**。在最短路径问题中有两个小考点分别为**Dijkstra****算法**和**Floyd****算法**。在本文，将对Dijkstra算法进行知识总结、讲解以及c++代码呈现。

目的

要求

思想

手动实现

时间复杂度

代码实现

参考文献

--------------------

## 目的 ##

求一个带权有向图中某个定点到其他各个顶点的最短路径，即**解决单源图的最短路径问题。**

## 要求 ##

1.  **源点无论经过多少个中间点均有机会到达此图各个顶点**，否则不存在到该顶点的最短路径。
2.  各个边的**权值必须为正数**。

## 思想 ##

举个例子，假如你现在正在乘坐泰坦尼克号在广袤的大海上旅行，突然船撞倒了冰山上（从现在开始，剧情变化了），所有的人都在逃生。你现在有幸跳到了一艘救生艇上，现在救生艇下面漂着100个人，你和这100个人之间或多或少的都有些联系，救生艇能将你们所有人救出来，但救生艇每次只能上一个人，在忽略人员性别等问题，单纯从和你相关关系的角度出发的情况下，请问怎么救人？

在题目中“你”是一个只看私人感情的人，毋庸置疑，得先救出和自己关系最好的人小A，然后再从｛自己与水中人的关系，自己与小A的关系+小A与水中人的关系｝中进行比较选出最好关系对，并由其去救起小B，下面类似的从｛自己与水中人的关系，自己与小A的关系+小A与水中人的关系，自己与小A的关系+小A与小B的关系+小B与水中人的关系，自己与小B的关系+小B与水中人的关系｝中进行比较选出最好的关系对，并由其救起小C，以此类推，直至将所有落水者救出为止。（注：本例子只用作辅助理解，并无其他意思。）

在救人的过程中，我们需要两个名单作为记录，一个用于记录各个落水者与“你”的关系程度，一个用于记录救起各个落水者的人员。

用算法的语言来描述如下：

**arcs\[\]\[\]****：**记录各个顶点到其它顶点的直接长度。（“你”和各个落水者的直接关系）

**s\[\]****：**用于记录已求得的最短路径的节点。（被救起的落水者）

v\[\]：为原始的顶点集合。

**path\[\]****：**记录源点到各个节点的最短路径的前驱节点（救起各个落水者的人员），初始值为arcs\[v0\]\[i\]（和“你”的关系）。

**dist\[\]****：**记录源点到各个节点的最短路径长度。（关系）

假设从v0出发，初始化：s=｛v0｝，dist\[i\]=arcs\[v0\]\[i\]，path\[i\] = v0，i为集合v剩余节点，v=v-s（在集合v中去掉初始点）

while(v集合不为空)｛

从集合v中选出一个顶点vj，它满足dist\[vj\] = Min\{dist\[vi\],vi属于v\}，此点即为从v0出发的一条最短路径的终s=s+\{vj\} v=v-\{vj\}

如果是第一趟选出的点，则令path\[vj\] = v0

修改最短路径dist ，对于v中的任意一个顶点vk，若dist\[vk\] > dist\[vj\] + arcs\[vj\]\[vk\] , 则令dist\[vk\]=dist\[vj\]+arcs\[vj\]\[vk\]，path\[vk\] = vj

｝

## 手动实现 ##

以2016年计算机联考真题为例，

如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70][]

从顶点1出发，初始化

距离最短的是的<1,5>,将点5添加到s中；修改dist值。

经计算比较发dist最小的是<1,2>,将点2添加到s中，修改dist值。

经计算比较发dist最小的是<2,3>,将点3添加到s中，修改dist值。

经计算比较发dist最小的是<5,6>,将点6添加到s中，修改dist值。

经计算比较发dist最小的是<5,4>,将点4添加到s中，修改dist值。

计算结束。s序列为1 5 2 3 6 4

当然考试的时候没必要将所有的步骤写出来，要做到又快又准。

## 时间复杂度 ##

本算法是基于贪心策略的。算法的主要部分是由双重循环组成的，第一层循环每次求出一个符合要求的点及其最短路径，内层循环是进行遍历以查找最短路径，其时间复杂度为o(|v|^2),其中|v|为所有顶点数。当把各个点都看成顶点进行算法执行时，需要执行|v|次算法，则此时算法的时间复杂度为 o(|v|^3)。

## 代码实现 ##

最近有些朋友在搞数模用到了这个算法，自己就顺带先复习一下这个算法。

/*编译环境：
 win10专业版
 DEV C++ 5.11
 TDM-GCC 4.9.2 64bit
 */
 
 #include<iostream>
 #include<stdio.h>
 #include<stack>
 #define INF 65535
 #define Max 5 
 using namespace std;
 
 int pp[(Max+1)*3] ;
 
 void Dijkstra(int arcs[][Max+1],int n,int v0){
 	int path[n+1] ;
 	int dist[n+1] ;//此两项无需初始化 
 	int s[n+1] = {2};//第一项初始化，s[0]记录旧集合开始的下标 
 	int i,j,k,min = INF,temp,v1;
 	bool change=1;//标记，防止图不连通形成死循环 
 	for(i=1;i<=n;i++){//dist和s赋初值 
 		dist[i] = arcs[v0][i];
 		s[i] = i ;
 		//cout<<dist[i]<<"\t";
 	}
 	
 	swap(s[1],s[v0]);
 	v1 = v0;
 	path[v0] = -1;
 	
 	while(s[0]!=n+1 && change){//未完全添加元素，且图连通 
 		change = 0;
 		min = dist[s[s[0]]]; 
 		temp = s[0];
 		i = s[0];
 		while(i<=n){//从未添加进的元素中进行遍历 
 			if(dist[s[i]]<min){//查找最近的点 
 				min = dist[s[i]]; 
 				temp = s[i];
 			} //if
 			i++; 
 		}//for
 		
 		j = s[0];	
 		while(s[j]!=temp)
 			j++;
 		if(s[0] == n)//已经遍历结束 
 			break;
 		else{
 			swap(s[s[0]],s[j]);
 			s[0]++;//将终点添加到s中
 			path[temp] = (v1==v0)?v1:path[temp]; //上一个点，并将其加入path
 			change = 1;
 		} //从此以下，添加点成功 
 
 		i = s[0];
 		while(i<=n){
 			if(dist[s[i]]>dist[temp]+arcs[temp][s[i]]){
 				dist[s[i]] = dist[temp]+arcs[temp][s[i]] ;
 				path[s[i]] = temp;	
 			}
 			i++;//if
 		}//while
 
 		v1 = temp;	
 
 	}//while
 	for(i = 1;i<=n;i++){
 		pp[i] = path[i];
 		pp[i+n] = dist[i];
 		pp[i+2*n] = s[i];
 	}
 	return ;
 }//fun
 
 
 int main(){
 	//变量声明 
 	int arcs[Max+1][Max+1];// = {
 {INF}};//初始化 
 	int v0;
 	int n;
 	stack<int> ss;
 	//int *pp;// [2][Max+1] 
 	//初始化 
 	for(int i = 0;i<=Max;i++)
 		for(int j = 0; j<=Max; j++)
 			arcs[i][j] = INF;
 	arcs[1][2] = 10;arcs[1][5] = 5 ;
 	arcs[2][3] = 1 ;arcs[2][5] = 2 ;
 	arcs[3][4] = 6 ;arcs[4][1] = 7 ;
 	arcs[4][3] = 6 ;arcs[5][2] = 3 ;
 	arcs[5][3] = 9 ;arcs[5][4] = 2 ;
 	n = 5;
 	v0 = 1;
 	
 	//执行算法 
 	Dijkstra(arcs,n,v0);
 	//输出
 	//插入顺序队列
 	cout<<"集合S：\t";
 	for(int i = 1;i<=n;i++)
 		cout<<pp[n*2+i]<<"\t";
 	cout<<"\n最短路径：\n";
 	for(int i = 2; i<=n ; i++){
 		int j = pp[n*2+i];
 		cout<<"第"<<i-1<<"趟:\t";
 		while(j!=1){
 			ss.push(j);
 			j = pp[j] ;
 		}
 		ss.push(j);
 		while(!ss.empty()){
 			cout<<ss.top(); 
 			ss.pop();
 			if(!ss.empty())
 				cout<<"→";
 		}
 		cout<<"\t,路径距离为 "<<pp[pp[n*2+i]+n]<<endl;
 	} 
 	cout<<"path数组：\t";
 	for(int i = 1; i<=n; i++)
 		cout<<pp[i]<<"\t";
 	cout<<endl; 
 	return 0;
 }

## 参考文献 ##

1.  严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.
2.  王道论坛 2019年数据结构考研复习指导\[M\]. 北京： 电子工业出版社，2018.

如有错误，还请各位不吝指正。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70]: /images/20211207/3021d6eec7ca4643a23b462de3a11aa8.png