（迪杰斯特拉）Dijkstra算法详解 PAT甲级 1003

清疚 2023-05-29 06:15 14阅读 0赞

## **1.迪杰斯特拉(Dijkstra)算法介绍** ##

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最 短路径。  
它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

光看介绍不好理解 ，我们拿PAT中甲级1003的题目来做例子讲解。

## 2.题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 1]  
解释下，就是N座城市（0-N-1），并且给你M行个距离，也就是从第3行开始到最后，分别意思为 从城市A到城市B的距离为C。后来两个数字是出发地，最后一个救援地。  
这里我们忽视题目中的救援之类的，我们只研究Dijkstra算法，要遍历出从出发点开始到各地的最短距离。

先上下代码和效果图（解释在后面）

#include <iostream>
    #include<cstring>
    #include <stdlib.h>
    #include <stdio.h>
    #include<cmath>
    #include<map>
    #include<vector>
    #include <sstream>
    #define MaxSize 500
    using namespace std;
    int main() { 
    	int method=1;
    	int n,m,cur,des;//城市个数，m为路径，cur为目前所在城市，des为目标城市
    	cin>>n>>m>>cur>>des;
    	int Graph[n][n];//存放图
    	int people[n];
    	int mindis[n];
    	int dis[n];
    	int hasdone[n];
    	int i;
    	int x,y,z;
    	for(i=0; i<n; i++) { 
    		int temp;
    		cin>>temp;
    		people[i]=temp;
    	}
    	for(i=0; i<n; i++) { 
    		dis[i]=MaxSize;
    		mindis[i]=MaxSize;//初始化
    		hasdone[i]=0;//0表示未求出最短路径 1表示已经求出最短路径
    	}
    	memset(Graph, -1, sizeof(Graph));
    	for(i=0; i<m; i++) { 
    		cin>>x>>y>>z;
    		Graph[x][y]=z;
    		Graph[y][x]=z;
    	}
    	//初始化两个动态数组
    	mindis[cur]=0;
    	hasdone[cur]=1;
    	int curat=cur;
    	for(int j=0; j<n-1; j++) { 
    		int min=MaxSize;
    		for(int i=0; i<n; i++) { 
    			if(hasdone[i]==0&&Graph[curat][i]!=-1) { 
    				if(dis[i]>(Graph[curat][i]+mindis[curat])) { 
    					dis[i]=Graph[curat][i]+mindis[curat];
    				}
    			}
    		}
    		int tempmin;
    		for(int i=0; i<n; i++) { 
    			if(hasdone[i]==0&&min>dis[i]) { 
    				min=dis[i];
    				tempmin=i;
    			}
    		}
    		mindis[tempmin]=min;
    		curat=tempmin;
    		hasdone[tempmin]=1;
    		cout<<curat<<endl;
    		for(int i=0; i<n; i++) { 
    			cout<<"到城市"<<i<<"最短距离"<<mindis[i]<<" "<<dis[i]<<" "<<hasdone[i]<<endl;
    		}
    		cout<<endl;
    	}
    
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 2]  
我们的核心思想是这样的  
我的代码中主要是三个数组 dismin\[\] 已经确认的最短路径 dis\[\] 当前正在循环的路径  
hasdone\[\] 辅助数组 1表示已经到达最短路径 0表示没有

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 4]

自己研究的，有理解不对的地方，请指出。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191104223645451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191104223714737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191104233405419.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191104225853812.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191104225751216.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDcxNDgwOA==,size_16,color_FFFFFF,t_70