算法实现步骤：
a.初始时，只包括源点，即S = {v}，v的距离为0。U包含除v以外的其他顶点，即：U ={其余顶点}，若v与U中顶点u有边，则(u,v)为正常权值，若u不是v的出边邻接点,则(u,v)权值 ∞;
b.从U中选取一个距离v最小的顶点k，把k，加入S中(该选定的距离就是v到k的最短路径长度)。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
动画模拟：
普通版Dijkstra代码如下：
#include#include#include#include
using namespacestd;int map[100][100];int vis[100];int way[100];intn,e,w,s;intmain(){
freopen("dij.in","r",stdin);
freopen("dij.out","w",stdout);int i,j,x,y,z,w,mi=20000;
scanf("%d%d",&n,&e);for(i=1;i<=e;i++)
{
scanf("%d%d%d",&x,&y,&z);
map[x][y]=z;
map[y][x]=z;
}
memset(way,127,sizeof(way));
scanf("%d",&s);
way[s]=0;for(i=1;i
{for(j=1;j<=n;j++)if(way[j]
{
mi=way[j];
w=j;
}
vis[w]=1;for(j=1;j<=n;j++)if(map[w][j]!=0&&vis[j]==0&&way[j]>way[w]+map[w][j])
way[j]=way[w]+map[w][j];
}for(i=1;i<=n;i++)
printf("%d",way[i]);return 0;
}
那现在让我们分析一下复杂度，很明显高达O(N*N)，那当做一些题时不论内存还是时间都会爆，那就急需我们做一些优化了
Dijkstra的堆优化：
依旧是迪杰斯特拉算法的思想，寻找当前距离最小的点，然后将它标记为已经确定的点，用它来更新各个没被确定的点。
emmmm我们选择优先队列来确定每一个最小距离的点
例题：
代码如下：
#include
using namespacestd;structSYM{intto,next,w;
}edge[500010];structLKJ{intv,c;bool operator a.c;
}
};
priority_queue >q;int head[101000],vis[101000],tot,dis[101000],n,m,k;void add(int x,int y,intw){
edge[++tot].to=y;
edge[tot].w=w;
edge[tot].next=head[x];
head[x]=tot;
}void dij(ints){
dis[s]=0;
LKJ hh;hh.v=s;hh.c=0;
q.push(hh);while(!q.empty()){
LKJ tmp=q.top();q.pop();int x=tmp.v;if(vis[x]) continue;vis[x]=1;for(int i=head[x];i;i=edge[i].next)if(!vis[edge[i].to]&&dis[edge[i].to]>dis[x]+edge[i].w){
dis[edge[i].to]=dis[x]+edge[i].w;
hh.v=edge[i].to;hh.c=dis[edge[i].to];
q.push(hh);
}
}
}intmain(){
memset(dis,127,sizeof(dis));intx,y,w;
scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
}
dij(k);for(int i=1;i<=n;i++){if(dis[i]==2139062143) printf("2147483647");else printf("%d",dis[i]);
}return 0;
}
