图论最短路径之迪杰斯特拉算法 Dijkstra及堆优化

素颜马尾好姑娘i 2023-02-15 10:25 8阅读 0赞

#### 一、迪杰斯特拉算法简介 ####

Dijkstra算法是在图论中求一个顶点到其余各顶点的最短路径的算法，解决的是带权图中（有向无向均可）最短路径的计算，该算法需要求图中**无负权**边，目前是最快的**单源点**最短路径算法，时间复杂度是O(n*2*) 。其特点是从起点开始，用贪心的策略连接最近的且未被访问过的顶点，直到扩展到终点为止。

#### 二、实现原理 ####

**1、基本原理**  
借助一个一维数组存储所求顶点到各个顶点的初始距离，然后找到离所求点距离最近的点为确定距离，再借助这个点所能到的所有点，判断借助最近的点中转到和直接到哪个距离最近，将最近的存储起来（松弛），再找接下来离所求点第二近的点以此循环完所有点，依次松弛完所有点。

**2、主要思想**  
每次找到离源点（所求起点）最近的一个顶点，然后以该点为中心进行扩展，最终得到源点到其余所有点的最短路径。

**3、实现步骤**  
1、将所有顶点分为两部分：已知最短路程的顶点集合 P和未知最短路径的顶点集合 Q。最开始P中只有源点一个顶点。我们可用一个标记数组book记录哪些点在集合P中。例如对于某点i，若book\[ i \]为1，则表示这个顶点在集合P中，若为0则表示在集合Q中。  
2、设置源点s到各点的初始距离，源点s到自己的距离为0，即dis\[ s \]=0。若存在源点能直接到达的顶点i，则把dis\[i\]设为e\[s\]\[i\]。同时把所有源点不能直接到达的点设为正无穷。  
3、开始松弛：在集合Q的所有顶点中选择一个离源点s最近的顶点u（即dis\[ u \]最小）加入到集合P中，并枚举以点u为起点的所有边，对每一条边进行松弛操作。例如存在一条从顶点u到顶点v的边，则可通过u拓展一条从s到v的路径即s -> u -> v，这条路径的长度为dis\[ u \]+e\[ u \]\[ v \]，如果这个值比dis\[ v \]的值要小，我们可以用新值替代当前dis\[ v \]中的值。  
4、如此重复第三步，如果集合Q为空，则结束。最终dis数组中的值就是源点到各点的最短路径。

#### 三、代码模板 ####

#include<iostream>
    
    using namespace std;
    const int N = 110,INF = 0x3f;
    int e[N][N],dis[N],book[N];
    int n,m,u;
    
    void dijkstra(int s)	//s为源点即起点
    { 
    	for(int i = 1;i <= n;i++)	//将起点到每一个点的距离存入dis数组
    		dis[i] = e[s][i];
    	book[s] = 1;			//起点的最短距离已确定，标记起点
    	for(int i = 1;i < n;i++)	//循环除起点外所有点共n-1次
    	{ 
    		int minn = INF;
    		for(int j = 1;j <= n;j++)	//循环1-n所有点中未确定最短距离即book为0的点
    		{ 
    			if(dis[j] < minn && book[j] == 0)	//找出这些点中离源点最近的点
    			{ 
    				minn = dis[j];	//记录最近距离
    				u = j;		//记录最近的点
    			}
    		}
    		book[u] = 1;	//确定最近的点的最短距离，标记为1
    		for(int j = 1;j <= n;j++)	//循环1-n的所有点，并借助刚确定的u点作为中转点刷新最短距离
    			if(e[u][j] < INF)	//如果u点到j点有路
    				if(dis[j] > dis[u] + e[u][j])	//源点s到j点的距离大于借助u点中转的距离（就是源点到u的距离加u到j的距离）
    					dis[j] = dis[u] + e[u][j];	//更新源点到j点的最短距离
    	}
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m;
    	for(int i = 0;i <= n;i++)		//邻接矩阵初始化
    		for(int j = 0;j <= n;j++)
    			if(i == j)
    				e[i][j] = 0;
    			else
    				e[i][j] = INF;
    				
    	for(int i = 0;i < m;i++)	//存入各边
    	{ 
    		cin >> a >> b >> c;
    		e[a][b] = c;
    	}
    	
    	dijkstra(1);	//设1点为源点
    
    	for(int i = 1;i <= n;i++)	//dis数组就是求得的源点到各顶点的最短距离
    	cout << dis[i] << " ";
    
    	return 0;
    }

该算法时间复杂度为O(n*2*)，我们可以用堆这个数据结构来优化，用一个最小堆来代替dis数组，这样每次取出最小距离点的复杂度降为O(1)，所以这个复杂度就降为O((m+n)logn)

#### 四、堆优化 ####

**代码模板：**

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    typedef pair<int,int> PII;	//在堆中，用pair存储边的信息，因为既要存储边的终点，也要存储边的权值
    const int N = 50,INF = 0x3f;
    
    int e[N],ne[N],w[N],h[N],idx;	//邻接表存图
    int dis[N],n,m;
    bool book[N];	//判断某顶点是否已经确定
    priority_queue<PII,vector<PII>,greater<PII> > heap;	//建立最小堆heap
    
    void add(int a,int b,int c)	//链式前向星加边函数
    { 
    	e[idx] = b;
    	w[idx] = c;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    void dijkstra(int start)	//dijkstra函数模板
    { 
    	memset(dis,0x3f,sizeof dis);	//初始化dis数组
    	dis[start] = 0;		//对源点距离初始化为0
    	heap.push({ 0,start});	//将源点入堆，pair的first存距离，second存终点，因为最小堆默认以pair的first排序，我们要找的就是最短距离的边
    
    	while(!heap.empty())
    	{ 
    		int v = heap.top().second,d = heap.top().first;	//堆的顶就是最小的边
    		heap.pop();
    		if(book[v])	//如果某顶点已确定，就跳过，继续下一个
    			continue;
    		book[v] = 1;	//标记确定v顶点
    
    		for(int i = h[v];~i;i = ne[i])	//遍历v顶点出发的所有边
    		{ 
    			int j = e[i];
    			if(dis[j] > d + w[i])	//如果从v中转有更小距离，就更新dis数组，并且入堆
    			{ 
    				dis[j] = d + w[i];
    				heap.push({ dis[j],j});
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m;
    	memset(h,-1,sizeof h);
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> c;
    		add(a,b,c);
    	}
    
    	dijkstra(1);
    
    	for(int i = 1;i <= n;i++)
    		cout << dis[i] << " ";
    
    	return 0;
    }