最短路径—Dijkstra算法

想必大家一定会Floyd了吧，Floyd只要暴力的三个for就可以出来，代码好背，也好理解，但缺点就是时间复杂度高是O(n³)。

   于是今天就给大家带来一种时间复杂度是O(n²)，的算法：Dijkstra（迪杰斯特拉）。

   这个算法所求的是单源最短路，好比说你写好了Dijkstra的函数，那么只要输入点a的编号，就可算出图上每个点到这个点的距离。

  我先上一组数据（这是无向图）：

 

5 6
1 2 5
1 3 8
2 3 1
2 4 3
4 5 7
2 5 2

图大概是这个样子：

我们以1为源点，来求所有点到一号点的最短路径。

先建立一个dis数组，dis[i]表示第i号点到源点（1号点）的估计值，你可能会问为什么是估计值，因为这个估计值会不断更新，更新到一定次数就变成答案了，这个我们一会再说。

然后我们在建立一个临界矩阵，叫做：map，map[i][j]=v表示从i到j这条边的权值是v。

dis初始值除了源点本身都是无穷大。源点本身都是0.

先从1号点开始。一号点，map[1][2]=5,一号点离2号点是5，比无穷大要小，所以dis[2]从无穷大变成了5。顺便，我们用minn记录距离1号点最短的点，留着以后会用。

dis[0,5,∞,∞,∞]。minn=2。

然后搜到3号点，map[1][3]=8,距离是8，比原来的dis[3]的∞小，于是dis[3]=8。但是8比dis[2]的5要大，所以minn不更新。

dis[0,5,8,∞,∞]

接着分别搜索4,5号点，发现map[1][4],map[1][5]都是∞，所以就不更新。

现在，dis数组所呈现的明显不是最终答案，因为我们才更新一遍，现在我们开始第二次更新，第二次更新以什么为开始呢？就是以上一次我们存下来的，minn，相当于把2当源点，求所有点到它的最短路，加上它到真正的源点（1号点）的距离，就是我们要求的最短路。

从2号点开始，搜索3号点，map[2][3]=1，原本dis[3]=8，发现dis[2]+map[2][3]=5+1=6<dis[3](8)所以更新dis[3]为6，minn=3

dis[0,5,6,∞,∞] minn=3.

然后搜索4号点，map[2][4]=3,原本dis[4]=∞,所以，dis[2]+map[2][4]=5+3=8<dis[4](∞)所以更新dis[4]=8,因为map[2][4]=3,3>1,minn不更新。

dis[0,5,6,8,∞] minn=3.

接着搜索5号点，map[2][5]=2,5+2=7,7<∞,dis[5]=7minn不变。

dis[0,5,6,8,7]

二号点搜完，因为minn是3，继续搜索3号点。

三号点还是按照二号点的方法搜索，发现没有可以更新的，然后搜索四号。

四号搜5号点，发现8+7>5+2,所以依然不更新，然后跳出循环。

 现在的估计值就全部为确定值了：

dis[0,5,6,8,7]

这就是每个点到源点一号点的距离，我们来看一下代码（与上文不同，这个是模板）：

#include <stdio.h>
#include<string.h>
#include<queue>

using namespace std;
/*
* 使用优先队列优化Dijkstra算法
* 复杂度O(ElogE)
* 注意对vector<Edge>E[MAXN]进行初始化后加边
*/
const int INF = 0x3f3f3f3f;
const int MAXN = 1000010;
struct qnode
{
	int v;//点
	int c;//权值和
	qnode(int _v = 0, int _c = 0) :v(_v), c(_c) {}
	bool operator <(const qnode &r)const
	{
		return c>r.c;
	}
};
struct Edge
{
	int v, cost;//边的另一点和边的权值
	Edge(int _v = 0, int _cost = 0) :v(_v), cost(_cost) {}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n, int start)//点的编号从1开始
{
	memset(vis, false, sizeof(vis));
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	priority_queue<qnode>que;
	while (!que.empty())
		que.pop();
	dist[start] = 0;
	que.push(qnode(start, 0));
	qnode tmp;
	while (!que.empty())
	{
		tmp = que.top();
		que.pop();
		int u = tmp.v;
		if (vis[u])
			continue;
		vis[u] = true;
		for (int i = 0; i<E[u].size(); i++)//对当前点进行松弛
		{
			int v = E[tmp.v][i].v;//当前边的另一点
			int cost = E[u][i].cost;
			if (!vis[v] && dist[v]>dist[u] + cost)
			{
				dist[v] = dist[u] + cost;
				que.push(qnode(v, dist[v]));
			}
		}
	}
}
void addedge(int u, int v, int w)
{
	E[u].push_back(Edge(v, w));
}
int main()
{
	int n, m;
	while (~scanf("%d%d", &m, &n)) {//m:边数 n;点数
		for (int i = 1; i <= n; i++)
			E[i].clear();
		for (int i = 0; i < m; i++)
		{
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			addedge(u, v, w);
			//addedge(v,u,w);无向图
		}
		Dijkstra(n, 1);
		printf("%d\n", dist[n]);
		//单源最短路，dist[i]为从源点start到i的最短路
	}
	return 0;
}