dijkstra算法思路

目标：对于边权为正的有向图，我们试求1-->n的最小值

该算法思路：

1. 初始化1到1的距离为0，到2~n的距离为正无穷大

2. 从1n中找出距离1的最小的不确定的点（最初1n均视作不确定），则该点到1的距离最小值被确定

3. 用该点去更新与该点连通的不确定的点

4. 每重复一次2、3步骤即可确定一个点，则迭代n次即可确定所有点的最小距离

依据该思路，我们即可写出朴素版dijkstra

主体分作两个部分 1、找最小点：O(n^2) 2、进行更新O(m)

总时间复杂度O(m+n^2)

m对时间复杂度影响较小，故该算法适合稠密图，用邻接矩阵储存图

代码如下

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 510;

int n,m;
int g[N][N],st[N],dist[N];

int dijkstra(){
	memset(dist,0x3f,sizeof dist);
	dist[1] = 0;
	
	for(int i=1;i<=n-1;i++){
		int t = -1;
		for(int j=1;j<=n;j++)//从未确定的点中找到离1距离最小的点 
			if(!st[j]&&(t==-1||dist[t]>dist[j]))t = j;
			
		for(int j = 1;j<=n;j++)//用节点 t 去更新各点 
			dist[j]  =min(dist[j],g[t][j] + dist[t]);
		
		st[t] = true;	
	}
	
	if(dist[n] == 0x3f3f3f3f) return -1;
	return dist[n];
}

int main(){
	
	scanf("%d%d",&n,&m);
	
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z); 
		g[x][y] = min(g[x][y],z); 
	}
	
	printf("%d",dijkstra());
	
	return 0; 
}

注意点：

1. 在存边时需注意重边只需保留最小边
2. 对g数组需初始化，以避免更新dist时将非连通边更新
3. 第一重循环可以仅循环n-1次的原因是：已确定n-1个点则第n个点已为当前最小点，则已确定

堆优化dijkstra算法

观察上述算法，分析可知其时间复杂度瓶颈在于寻找到距离最小的点（n^n)

则我们考虑优化这一过程：堆能在O（1）的时间复杂度内找到集合中的最小值，我们用堆来维护所有不确定的点，以到1的距离排序，就可以解决O(n^2)找最小值的算法瓶颈

该算法思路

1. 初始化1到1的距离为0，到2~n的距离为正无穷大

2. 用堆来维护不确定的点，堆中存两个值：到1的距离 distence 和 该点的编号 ver distence 意义在于堆的排序

3. 将 distence = 0， ver = 1入堆

4. 每次取出堆顶元素，确保该点未确定时，遍历此点所连各点，更新各点 distence 的同时将各点入堆

5. 堆空时，即确定1到所有点的最小距离

主体为

1 找最小点：n*O(1) = O(n)

2 入堆 m * O(logn) = O(mlogn)

则该算法时间复杂度O(mlogn)

m对时间复杂度影响较大，当m值较大时其复杂度会超过朴素dijkstra（O(n^2+m)),故该算法使用于边数较少时（稀疏图），因而我们使用邻接表实现

代码如下

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int,int> PII;
const int N = 150010;

int h[N],e[N],ne[N],v[N],idx;
int dist[N],n,m;
bool st[N];

void add(int a,int b,int c){
    e[idx] = b;
    v[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII> > heap;
    dist[1] = 0;
    heap.push({0,1});
    
    while(heap.size()){
        PII t = heap.top();
        heap.pop();
        
        int ver = t.second,distence = t.first;
        
        if(st[ver])continue;
        st[ver] = true;
        
        for(int i = h[ver];i!=-1;i=ne[i]){
            int j = e[i];
            if(dist[j]> distence + v[i]){
                dist[j] = distence + v[i];
                heap.push({dist[j],j});
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f)return -1;
    else return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    
    memset(h,-1,sizeof h);
    
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    
    printf("%d",dijkstra());
    
    return 0;
}

注意点

1. 邻接表存储时，h数组的大小与ne、e、v数组大小含义不同（h：n，ne、e、v：m）仅当n与m的范围相同时才可以一致
2. 使用pair储存distence与ver，pair在比较大小时会优先比较first的大小，故distence需放在first的位置，不可颠倒

有关dijkstra算法正确性的证明 https://www.acwing.com/file_system/file/content/whole/index/content/7317949/