前言

此乃一个小 Oler 的一篇图论算法随笔，从今日后，还会进行详细的修订。

一、简单介绍（Dijkstra）

迪杰斯特拉算法 ( Dijkstra ) 是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

定义：

Dijkstra 算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

二、基本概念&用途

最短路径

路径长度：当图是带权图时，把从一个顶点 \(i\) 到图中其余任意一个顶点 \(j\) 的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度。
最短路径：把带权路径长度最短的那条路径称为最短路径。

备注：求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。

带权有向图 \(G\) 的最短路径问题一般可分为两类：

1）单源最短路径，求图中某一顶点到其他各顶点的最短路径。

2）多源最短路径，求每对顶点间的最短路径。

Dijkstra 的实战性/优劣势

Dijkstra 算法用于有权边的图，属于单源最短路径。
其对于一般其他的求解单源最短路的算法，优势在于基于空间复杂度平分秋色的情况下，时间复杂度更优，但由于是贪心思想，所以图中不可出现负边权，下面的算法流程会对此进行解释。
其算法内涵是设置一个集合 \(S\) 记录已求得的最短路径的顶点，初始时把源点 \(v_0\) 放入 \(S\) ，集合 \(S\) 每并入一个新顶点 \(v_i\) ，都要修改源点 \(v_0\) 到集合 \(V-S\) 中顶点当前的最短路径长度值。

三、算法流程（代码实现）

DIJ之【邻接矩阵】

I.储存边权

本种方法用邻接矩阵储存任意两个邻接节点 \(u\) 和 \(v\) 的边权值，引入一个辅助数组 \(acrs\) ，由于两个邻接节点之间可能会出现重边（即节点 \(u\) 到其邻接节点 \(v\) 有多条路径），所以我们只需要取其最小值。

\(arcs_{u,v}=\min(value<u,v>,arcs_{u,v})/\infty\) ：表示有向边<u,v>的权值

II.Dijkstra 函数

\(dist_i\)：记录源点到其他各节点 \(i\) 当前的最短路径长度

初始化：\(dist_{i}=acrs_{0,i}\)

总共进行 \(n-1\) 次操作，直到所有的顶点都访问过后结束。

①.找最短路终点

假设起始点为 \(v_0\) ，要求从 \(v_0\) 到 \(S \in {v}\) 的最短路径。

从顶点集合 \(V - S\) 中选出 \(v_j\) ，满足 \(dist_j=\min(dist_i|\in V-S)\) ，即 \(v_j\) 是从 \(v_i\) 出发到的所有邻接节点之中最短路径的顶点， \(v_j\) 就是当前求得的一条从 \(v_0\) 出发的最短路径的终点，然后再把 \(v_j\) 放入集合 \(S\) ，这里我们采用一个标记 bool 数组 \(f\) 进行标记。

②.修改最短路径

修改从起始点 \(v_0\) 出发到集合 \(V-S\) 上得任意一顶点 \(v_k\) 可达的最短路径长度 \(dist_k\) 。

若 \(dist_j+arcs_{j,k}<dist_k\) ，则更新 \(dist_k=dist_t+arcs_{t,k}\) 。

步骤如下图所示，源点为 \(v_0\) ，初始时集合\(S=\){\(v_0\)}，\(dist_1=3\)，\(dist_2=7\)，当将 \(v_1\) 并入集合 \(S\) 后，\(dist_2\) 需要更新为 \(4\) 。

模拟 Dijkstra 过程

III. Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int oo=0x3f3f3f3f;
const int N=10001;
int n,m,s,u,v,w;
int dist[N],arcs[N][N];
bool f[N];
void dijkstra() {
	dist[s]=0;   //初始化
	for(int i=1;i<=n;i++) {   //循环n次，每次选择一个点加入集合V
		int t=-1;
		for(int j=1;j<=n;j++) {    //寻找值最小的顶点
			if(f[j]==0&&(t==-1||dist[j]<dist[t])) 
				t=j;
		}
		f[t]=1;   //标志位，把点加入集合S
		for(int k=1;k<=n;k++) {   //更新dist的值 
			if(f[k]==0&&dist[t]+arcs[t][k]<dist[k])
				dist[k]=dist[t]+arcs[t][k];
		}
	}
	return ;
}
signed main() {
	scanf("%lld%lld%lld",&n,&m,&s);   //输入点数、边数和起始点
	memset(dist,oo,sizeof dist);
	memset(arcs,oo,sizeof arcs);
	while(m--) {
		scanf("%lld%lld%lld",&u,&v,&w);
		arcs[u][v]=min(arcs[u][v],w);   //每次更新为最小值
	}
	dijkstra();
	for(int i=1;i<=n;i++)
		printf("%lld ",dist[i]);
	printf("\n");
	return 0;
}

DIJ之【邻接表+堆优化】

I.邻接表存图

由于要使用到优先队列堆优化 Dijkstra 的运行效率，而邻接矩阵在遍历时要对于每个顶点去找其最短的路径终点，会大大增加运行时间，所以我们的“开国元老”邻接矩阵 \(arcs\) 已经不适用 ~~（落伍了）~~ ，需要排上我们的年轻小将“车骑将军”邻接表 \(adj\) ，此将军甚是威猛，其与老将军不同的最大特点是在访问时只需遍历其相邻的边。

II.Dijkstra 遍历函数

还是 \(dist_i\)：记录源点到其他各节点 \(i\) 当前的最短路径长度

优化思路：在朴素版的 Dijkstra 遍历所有点比较找出距离最近的点使用优先队列priority_queue 进行优化。

①.定义优先队列

将优先队列定义成小根堆，优先队列元素为 \(pair<int,int>\) ，其中第一个元素含义为源点 \(v_0\) 到某个顶点 \(v_j\) 的距离 \(dist_j\) ，第二个元素为节点编号 \(v_j\) 。

②.初始化

初始化：\(dist_i=\infty\)

将源点 \(dist[v_0]\) 设置成 \(0\) ，并将 {\(dist[v_0],v_0\)} 放入优先队列。

③.更新最短路径

去取出栈顶的元素，如果，堆顶节点 \(v_j\) 已经在集合 \(S\) 中，则舍弃该点，再次取出堆顶元素，否则把该节点 \(v_j\) 加入堆集合 \(q\)，修改从源点 \(v_0\) 出发到集合 \(V-S\) 内任意一点 \(v_k\) 可达的最短路径长度 \(dist[k]\) ；若 \(dist[k]>dist[j]+value<j,k>\) 则更新 \(dist[k]=dist[j]+value<j,k>\)，其中 \(value<j,k>\) 代表 \(v_j\) 到 \(v_k\) 的权值。并把节点 { \(dist[k],k\) } 加入队列中。

III. Code（PRIORITY）

#include<bits/stdc++.h>
#define int long long
#define M(x,y) make_pair(x,y)
using namespace std; 
typedef pair<int,int> pll; 
const int inf=2147483647;
const int N=1e6+10; 
int n,m,s,x,y,z;
struct Node {   //稀疏图用邻接表来存
	int to,w,nxt;
	Node() {
		to=nxt=w=0;
	}
	Node(int a,int b,int c) {
		to=a;
		nxt=b;
		w=c;
	}
}adj[N];
int head[N],idx;
int dist[N];
bool st[N];   //如果true说明这个最短路径已经确定
priority_queue<pll,vector<pll>,greater<pll> >heap; 
inline void add(int x,int y,int z) {
	adj[++idx]=Node(y,head[x],z);
	head[x]=idx;
}
void dijkstra() {
	for(int i=1;i<=n;i++)
		dist[i]=inf;
	dist[s]=0;
	heap.push(M(0,s));  //这个顺序不能倒
	while(!heap.empty()) {
		pll k=heap.top();    //取不在集合S（V-S）中距离最近的点
		heap.pop();
		int u=k.second;
		int distance=k.first;
		if(st[u]) continue;
		st[u]=1;   //把该点加入集合S
		for(int i=head[u];i;i=adj[i].nxt) {
			int v=adj[i].to,w=adj[i].w;    //取出和ver相连的点和边权
			if(dist[v]>distance+w) {
				dist[v]=distance+w;    //更新最短路
				heap.push(M(dist[v],v));     //放入优先队列中
			}
		}
	} 
	return ;
}
signed main() {
	scanf("%lld%lld%lld",&n,&m,&s);
	while(m--) {
		scanf("%lld%lld%lld",&x,&y,&z);
		add(x,y,z);
	}
	dijkstra();
	for(int i=1;i<=n;i++)
		printf("%lld ",dist[i]);
	printf("\n");
	return 0;
}