1 简介

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

PS：此算法不能用于求负权图，要求所有边的权重都为非负值。

2 算法思想与原理

dijkstra 算法思想是基于贪心算法思想的。所谓贪心算法即始终保持当前迭代解为当前最优解。意思就是在已知的条件下或是当前拥有的全部条件下保证最优解，若在此后的迭代中由于加入了新的条件使得产生了更优解则替代此前的最优解。通过不断的迭代不断保证每次迭代的结果都是当前最优解，那么当迭代到最后一轮时得到的就会是全局最优解。 由于下一轮迭代会参考上一轮的最优解，因此每一轮的迭代的工作量基本一致，降低了整体工作的复杂性。

在最短路径的问题中，局部最优解即当前的最短路径或者说是在当前的已知条件下起点到其余各点的最短距离。关键就在于已知条件，这也是 Dijkstra 算法最精妙的地方。我们来解释一下。

对于 Dijkstra 算法，我们假设初始集合（也就是初始条件）不存在任何顶点的，即所有顶点之间是不存在任何路径的，即我们认为所有顶点之间的距离都是无穷大。那么开始加入新的条件，因为我们已知源点距源点距离最小，所以加入进去，并加入它的边，在该条件下，更新该源点到其余顶点的最短距离，选出没有加入到已知集合的距源点距离最小的点，此点最短距离也被确定了（因为其他路径都比这条路径大，无法通过其他路径间接到达这个顶点使得路径更小），然后加入该点与其余还未加入已知条件顶点的边，并以该点迭代刷新最短距离。再重复以上操作，直至所有顶点都加入已知条件集合。

3 具体步骤

1. 选择起点 start 与终点 end ；

2. 所有点除起点外加入未知集合，并将起点加入已知集合，即至标志位为真，意为已确定该点到源点的最短路径；

3. 初始化计算，更新起点与其他各点的距离 dis(start,n);

4. 在未知的点集合中，选择 dis(start,n)中值最小的点 x ，将 x 加入已知点集合。

5. 对于剩余顶点中，计算 dis(start,n) > dis(start,x)+dis(x,n)，若真则dis(start,n)=dis(start,x)+dis(x,n)，此时 start 与 n 点路径经过 x 点。循环直至目标点 (dest ) 加入已知列表，取得 dis(start,dest) 即为最短距离。

4 动态展示

5 代码实现

int dis[1001];
bool f[1001];

#define INF 0x3f3f3f3f
void Dijkstra(int s) // s 是起点，e 是终点 
{
	memset(dis,0x3f,sizeof(dis)); // 默认情况，start 点到各个点的距离都为无穷大
	memset(f, 0, sizeof f); // 把所有的点都清楚标记，表示还没加入到集合
	
	dis[s] = 0;

	int p,mind; 
	while(1) // 这里循环 n-1 次也行，最多也就是循环 n-1 次 
	{
		mind=INF;
		// 在没有加入集合的点里面找出距离 s 最近的那个点 p
		for(int i=1;i<=n;i++){
			if(!f[i] && dis[i]<mind){
				mind=dis[i];
				p=i;
			} 
		}

		if(mind==INF) return; // 没有找到新的点
		f[p] = true; // 把 p 点加入到已知点的集合

		//以 p 作为跳转点，去探寻更远的点，更新和这些点的距离 
		for(int i=h[u];i;i=e[i].next){
			v = e[i].to;
			if(!f[v] && v[p][i]&&dis[i]>dis[p]+e[i].w)
				dis[i] = dis[p] + e[i].w; 
		}
	}
}

6. Dijkstra 的堆优化

上面的程序是一个 $O(n^2)$ 的程序，但可以通过堆排序进行优化。我们记录每个点距离 s 的距离，并且排序，就能在未加入集合的点里找到距离 s 最近的点。找到新的点之后，要用这个点去更新其余点的距离，所以数据要动态变化，我们用堆排序比较合适。

struct Node{
	int point, dis;
};

//重载 < 运算符才能建立优先队列
bool operator < (const Node i, const Node j){
	return i.dis>j.dis:
}

int dis[1001];
bool f[1001];

#define INF 0x3f3f3f3f
void Dijkstra(int s) // s 是起点，e 是终点 
{
	memset(dis,0x3f,sizeof(dis)); // 默认情况，start 点到各个点的距离都为无穷大
	memset(f, 0, sizeof f); // 把所有的点都清楚标记，表示还没加入到集合
	priority_queue < Node > q;
	
	dis[s] = 0;
	q.push({s,0});

	while(1) // 这里循环 n-1 次也行，最多也就是循环 n-1 次 
	{
		// 在没有加入集合的点里面找出距离 s 最近的那个点 p
		int p = q.front().point;
		q.pop();
		
		if(!f[p]){
			f[p] = true; // 把 p 点加入到已知点的集合

			//以 p 作为跳转点，去探寻更远的点，更新和这些点的距离 
			for(int i=h[u];i;i=e[i].next){
				v = e[i].to;
				if(!f[v] && v[p][i]&&dis[i]>dis[p]+e[i].w){
					dis[v] = dis[p] + e[i].w; 
					q.push({v,dis[v]};)
				}
			}
		}
	}
}

上面的代码的时间复杂度为 $O(n \log n) + O(m)$。当题目中 n 和 m 都很大的时候，这个算法就很有优势。