最短路径（迪杰斯特拉）Dijkstra算法的理解

心已赠人 2023-10-11 14:52 34阅读 0赞

### 最短路径（迪杰斯特拉）Dijkstra算法的理解 ###

##### 1.定义概览 #####

Dijkstra(迪杰斯特拉)算法是典型的**单源最短路径算法**，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。**注意该算法要求图中不存在负权边。**

**问题描述**：在无向图 G=(V,E) 中，（其中V代表点集， E代表边集）。假设每条边 E\[i\] 的长度为 w\[i\]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

**算法描述**：每次确定dis数组的一个值，确定初始化节点到第i个节点的值，并更新确定节点到其他节点的值的大小。我对此算法的理解就是局部贪心。

**算法步骤**：

1.  声明邻接矩阵map，dis数组，以及vis数组。

> map\[i\]\[j\]代表 i 节点到 j 节点的距离  
> dis\[i\]代表源点到第 i 个节点的最短距离  
> vis\[i\]代表源点到第 i 个节点最短距离已经确定，取值为0或者1，起到标志性作用

1.  初始化：

> 矩阵上对角线上的元素设置为0，其余元素设置为Inf(无穷大)  
> vis数组所有元素初始化为0

1.  对输入的数据进行处理

> 输入x y len  
> 矩阵元素赋值：map\[x\]\[y\]=len; map\[y\]\[x\]=len;  
> 代表u到v的距离为w，因为无向图所以矩阵对角线两边的元素都需要赋值为w

1.  对dis数组进行赋值

> 源点已经确定的情况下，对dis\[i\] = map\[u\]\[i\]，代表源点u到i点的距离。并更新vis\[u\] = 1， 代表源点到源点的最短距离已经确定，当然这里只是起到标志作用，dis\[u\] = 0！

1.  找到源点u到其他 n-1 个点的距离

> 首先需要遍历dis数组，找到最短距离（相等的最短距离不用纠结，顺序记录就好），并记录索引 temp  
> 更新vis\[temp\] = 1，代表源点到temp索引的最短距离已经找到，距离为dis\[temp\]!

1.  在5步骤找到的temp索引的基础上更新temp到其他vis\[i\]=0点的就最短距离

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxOTU2Ng_size_16_color_FFFFFF_t_70_pic_center]

代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define Inf 0x3f3f3f3f
    
    using namespace std;
    
    int map[1005][1005];
    
    int vis[1005],dis[1005];
    int n,m;//n个点，m条边
    
    void Init ()
    {
        
    	memset(map,Inf,sizeof(map));
    	for(int i=1;i<=n;i++)
    	{
        
    		map[i][i]=0;
    	}
    }
    
    void Getmap()
    {
        
    	int u,v,w;
        for(int t=1;t<=m;t++)//无向图赋值
    	{
        
    	  	scanf("%d%d%d",&u,&v,&w);
    	  	if(map[u][v]>w)
    		  {
        
    		  map[u][v]=w;
    		  map[v][u]=w;
    	      }
    	}
    
    }
    
    void Dijkstra(int u)
    {
        
    	memset(vis,0,sizeof(vis));//vis 为标志数组，1的时候代表当前最短已经确定
    	for(int t=1;t<=n;t++)
    	{
        
    		dis[t]=map[u][t];
    	}
    	vis[u]=1;
    	for(int t=1;t<n;t++)//循环 n-1 次，找到当前点到其他 n-1 个点的距离
    	{
        
    		int minn=Inf,temp;
    		for(int i=1;i<=n;i++)
    		{
        
    			if(!vis[i]&&dis[i]<minn)
    			{
        
    				minn=dis[i];
    				temp=i;
    			}
    		}
    		vis[temp]=1;
    		for(int i=1;i<=n;i++)
    		{
        
    			if(dis[temp] + map[temp][i]<dis[i] && vis[i]==0)
    			{
        
    				dis[i]=map[temp][i]+dis[temp];
    			}
    		}
    	}
    
    }
    
    int main()
    {
        
    	/*
    		6 9
    		1 2 1
    		1 3 12
    		2 3 9
    		2 4 3
    		3 4 4
    		3 5 5
    		4 5 13
    		5 6 4
    		4 6 15
    	*/
    
    	scanf("%d%d",&n,&m);
    	Init();
    	Getmap();
    	Dijkstra(1);//求1点到所有点的最短路径
    	for(int i = 1; i <= n; i ++)
    		cout << dis[i] << " ";
    
    
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxOTU2Ng_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201014114956718.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxOTU2Ng==,size_16,color_FFFFFF,t_70#pic_center