图论最短路径算法（二）Dijkstra算法（迪杰斯特拉算法）

不念不忘少年蓝@ 2021-09-22 23:48 554阅读 0赞

### 文章目录 ###

*   *   *  【初识】
         *  【算法描述】
         *  【算法分析&思想讲解】
         *  【算法图解】
         *  【应用场景】
         *   *  【例1】最短路径问题
             *  【例2】最小花费

### 【初识】 ###

> Dijkstra算法用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。

> Dijkstra的时间复杂度是O (N2)，它不能处理存在负边权的情况。

### 【算法描述】 ###

设起点为s，dis\[v\]表示从s到v的最短路径，pre\[v\]为v的前驱节点，用来输出路径。

a)初始化：dis\[v\]=∞(v≠s); dis\[s\]=0; pre\[s\]=0;

b)For (i = 1; i <= n ; i++)

1.  在没有被访问过的点中找一个顶点u使得dis\[u\]是最小的。
2.  u标记为已确定最短路径
3.  For 与u相连的每个未确定最短路径的顶点v  
    if (dis\[u\]+w\[u\]\[v\] < dis\[v\])  
    \{  
    dis\[v\] = dis\[u\] + w\[u\]\[v\];  
    pre\[v\] = u;  
    \}

c)算法结束：dis\[v\]为s到v的最短距离；pre\[v\]为v的前驱节点，用来输出路径。

### 【算法分析&思想讲解】 ###

从起点到一个点的最短路径一定会经过至少一个“中转点”（例如下图1到5的最短路径，中转点是2。特殊地，我们认为起点1也是一个“中转点”）。显而易见，如果我们想求出起点到一个点的最短路径，那我们必然要先求出中转点的最短路径（例如我们必须先求出点2 的最短路径后，才能求出从起点到5的最短路径）。

换句话说，如果起点1到某一点V0的最短路径要经过中转点Vi，那么中转点Vi一定是先于V0被确定了最短路径的点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

我们把点分为两类，一类是已确定最短路径的点，称为“白点”，另一类是未确定最短路径的点，称为“蓝点”。如果我们要求出一个点的最短路径，就是把这个点由蓝点变为白点。从起点到蓝点的最短路径上的中转点在这个时刻只能是白点。

Dijkstra的算法思想，就是一开始将起点到起点的距离标记为0，而后进行n次循环，每次找出一个到起点距离dis\[u\]最短的点u，将它从蓝点变为白点。随后枚举所有的蓝点vi，如果以此白点为中转到达蓝点vi的路径dis\[u\]+w\[u\]\[vi\]更短的话，这将它作为vi的“更短路径”dis\[vi\]（此时还不确定是不是vi的最短路径）。

就这样，我们每找到一个白点，就尝试着用它修改其他所有的蓝点。中转点先于终点变成白点，故每一个终点一定能够被它的最后一个中转点所修改，而求得最短路径。

### 【算法图解】 ###

*  算法开始时，作为起点的dis\[1\] = 0，其他的点dis\[i\] = 0x7fffffff。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]
 *  这时dis\[2\]，dis\[3\]，dis\[4\]被它的最后一个中转点1修改为了最短路径。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 2]
 *  这时dis\[3\]，dis\[5\]被它们的最后一个中转点2修改为了最短路径。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 3]
 *  这时dis\[4\]也被它的最后一个中转点3修改为了最短路径。
 *  接下来的两轮循环将4、5也变成白点。N轮循环结束后，所有的点的最短路径即能求出。

### 【应用场景】 ###

#### 【例1】最短路径问题 ####

**【问题描述】**  
　　平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。  
　　  
　　若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的  
　　  
　　任务是找出从一点到另一点之间的最短路径。  
　　  
**【输入格式】**  
　　输入，共n+m+3行，其中:  
　　  
　　第一行为整数n。  
　　  
　　第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。  
　　  
　　第n+2行为一个整数m，表示图中连线的个数。  
　　  
　　此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。  
　　  
　　最后一行：两个整数s和t，分别表示源点和目标点。  
　　  
**【输出格式】**  
　　输出，两行，一个实数（保留两位小数），表示从s到t的最短路径长度。  
　　另一行输出路径

**【输入样例】**  
5  
0 0  
2 0  
2 2  
0 2  
3 1  
5  
1 2  
1 3  
1 4  
2 5  
3 5  
1 5

**【输出样例】**  
3.41  
5<-2<-1

**【实例代码】**

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    
    using namespace std;
    
    const int N = 1000;
    int i,j,n,m,x,y,l,k;
    double temp,minn,maxx;
    int a[N][3],pre[N];
    double w[N][N],dis[N];
    bool b[N];
    
    //求a,b之间的最短路径，以及打印路径 
    void bfs(int a, int c){ 
    	maxx = 0x7f;
    	memset(dis,maxx,sizeof(dis));
    	memset(pre,0,sizeof(pre));
    	memset(b,1,sizeof(b));//用来标识图中的点是否被遍历,true代表蓝点，未遍历 
    
    	//初始化起点相关数值 
    	dis[a] = 0;
    	b[a] = false; 
    	pre[a] = 0;
    
    	for(i=1; i<=n; i++){ //起点能够直接相连的点赋值 
    		dis[i] = w[a][i];
    	}
    	
    	for(i=1; i<=n-1; i++){ //寻找起点到剩余n-1个点的最短路径 
    	
    		minn = maxx;//minn是一个中间量,用来作为暂存最小值 
    		l = 0;//用来记录中间路径
    		for(j=1; j<=n; j++){ //寻找合适的蓝点变成白点 
    			if(b[j] && dis[j]<minn){ 
    				minn = dis[j];
    				l = j;
    			} 
    		}
    		
    		if(l == 0) break; //没有蓝点变成白点
    		
    		b[l] = false;//把蓝点变白 
    		
    		for(j=1; j<=n; j++){ //更新由于新白点形成的dis
    			 if(dis[l]+w[l][j]<dis[j]){ 
    			 	dis[j] =  dis[l] + w[l][j];
    			 	pre[j] = l;
    			 }
    		}
    		
    	}
    	printf("%.2lf\n",dis[c]);
    	
    	//print path
    	k = c;
    	while(k!=0){ 
    		cout<<k<<"<-";	
    		k = pre[k];
    	}
    	cout<<a;
    	 
    }
    
    int main(){ 
    	cin>>n;
    	for(i=1; i<=n; i++){ 
    		cin>>a[i][1]>>a[i][2];
    	}
    	memset(w,0x7f,sizeof(w));
    	cin>>m;
    	for(i=1; i<=m; i++){ 
    		cin>>x>>y;
    		temp = sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
    		w[x][y] = w[y][x] = temp;
    	}
    	cin>>i>>j;
    	bfs(i,j);
    	return 0;
    }

#### 【例2】最小花费 ####

**【问题描述】**  
在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。

**【输入格式】**  
第一行输入两个正整数n,m，分别表示总人数和可以互相转账的人的对数。

以下m行每行输入三个正整数x,y,z，表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费 (z<100)。

最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。

**【输出格式】**

输出A使得B到账100元最少需要的总费用。精确到小数点后8位。  
**【输入样例】**

3 3  
1 2 1  
2 3 2  
1 3 3  
1 3  
**【输出样例】**

103.07153164  
**【数据规模】**

1<=n<=2000

**【参考程序】**

#include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    
    using namespace std;
    
    const int N = 1000;
    int i,j,n,m,x,y,l,k;
    double temp,minn,maxx;
    int a[N][4],pre[N];
    double w[N][N],dis[N];//用来存储从起点到当前节点的最少钱数，初始化为0x7f 
    int b[N];//表示是否遍历到 ，初始化=1，表示蓝点 
    
    int main(){ 
    	cin>>n>>m;
    	maxx = 0x7f;
    	memset(w,maxx,sizeof(w));
    	for(i=1; i<=m; i++){ 
    		cin>>x>>y;
    		cin>>w[x][y];
    	}
    	
    	cin>>x>>y;//输入起点和终点 
    	
    	memset(b,1,sizeof(b));
    	memset(dis,0,sizeof(dis));
    	memset(pre,0,sizeof(pre)); 
    	dis[x] = 100;//假设起点的钱数=100
    	
    	for(i=1; i<n; i++){ //至多遍历n-1次就可以 
    		minn = 0;
    		l = 0;
    		for(j=1; j<=n; j++){ 
    			if(b[j] && dis[j]>minn){ 
    				minn = dis[j];
    				l = j;
    			}
    		}
    		if(l == 0) break;
    		b[l] = 0;
    		for(j=1; j<=n; j++){ 
    			if(w[l][j]<maxx){ //代表l,j之间有通路
    				temp = 1-w[l][j]/100;//利率 
    				if(dis[l]*temp > dis[j]){ 
    					dis[j] = dis[l] * temp;
    				}	
    			}	
    		}
    	} 
    	
    	temp = 100*100/dis[y];
    	printf("%.8lf\n",temp);
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/f519f18b66f9428180cd04b9f519b701.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/d95df6e96e7a4b78a60cbac4feca337d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 2]: /images/20210920/ae19d824a32a4d949147fd616f4d8580.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 3]: /images/20210920/6b533385e62948999cdda30f0fcf6e2f.png