浅谈最短路之——迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉算法复杂度为O(n^2)，加入堆优化后可以优化到O((m+n)logn)的级别。主要适用于解决不含负边权的单源最短路。其基本思想是：记S为已找到源点的最短路的点的集合，V为不在集合S中的点的集合，用dis数组记录i到源点的最短路径长度，每次取V中w值最小的v加入S，更新dis的值，重复上述步骤直到所有点都在S中，这样dis[t]即为最短路径长度。

      而我们发现，如果边数不足n^2，我们可以用堆来优化这个过程，每次取出最短路时并不需要遍历一遍V，只需弹出堆顶元素即可，因为c++默认堆为大根堆，所以只需在压入时将dis取负即可；每次调整的复杂度为O(elogn)，e为该点连的边数所以最后的复杂度就降到了O((m+n)logn)。

       接下来给一段图示：

对于这个图，我们要求找出1-7的最短路径长度。

    第一步：源点1在集合S中，dis[1]=0，找到w最小的边，连向4，dis[4]更新为5，4进入集合S，找到3，dis[3]更新为5+2=7，3进入集合S，找到2，dis[2]更新为7+3=10，2进入集合S，发现dis[2]+w[1,2]>dis[1]，且2没有其他边了，退回到3，找到下一条边5，dis[5]=7+4=11，最后找到dis[7]=11+1=12。然后退回到4，找到第二小的边连向6，dis[6]更新为5+4=9，然后无法更新dis[1]，退回。

   第二步：源点1找到第二小边，连向2，dis[2]更新为6，然后发现2无法更新任何dis，返回。

   第三步：源点1找到下一条边，连向6，dis[6]更新为8，然后无法继续更新dis，返回，1已经没有其他边了，算法结束。

下面贴一段堆优化的迪杰斯特拉算法代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int Read()
{
	int i=0,f=1;
	char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-')
	{
		f=-1,c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar())
	  i=(i<<3)+(i<<1)+c-'0';
	return i*f;
}

const int N=1e4+5,M=2e5+5,INF=0x3f3f3f3f;
int n,m,tot,st;
int dis[N];
int first[N],next[M],to[M],w[M];
priority_queue<pair<int,int> >q;

void add(int x,int y,int z)
{
	tot++;
	next[tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	w[tot]=z;
}

void dijkstra()
{
	memset(dis,INF,sizeof(dis));
	dis[st]=0;
	q.push(make_pair(0,st));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		for(int e=first[u];e;e=next[e])
		{
			int v=to[e];
			if(dis[u]+w[e]<dis[v])
			{
				dis[v]=dis[u]+w[e];
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}

int main()
{
	int x,y,z;
	n=Read();m=Read();st=Read();
	for(int i=1;i<=m;++i)
	{
		x=Read();y=Read();z=Read();
		add(x,y,z);add(y,x,z);
	}
	dijkstra();
	cout<<dis[n];
	return 0;
}