Dijkstra（单源最短路径）

Dijkstra（单源最短路径）

算法思想
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
基本思路
(1) 初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3)，直到遍历完所有顶点。

图解过程

#include<bits/stdc++.h>
using namespace std;
int n,m,dist[1000],g[1000][1000]; //dist储存最短路  
bool book[1000];
void dijkstra()
{
	memset(dist,8,sizeof(dist)); //赋最大值 
	dist[1]=0;  //第一个点即源点 最短路为0 
	for(int i=0;i<n-1;i++) //外层循环n-1次 最后一个不需循环 
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		{
			if(!book[j]&&(t==-1||dist[j]<dist[t])) //未做过源点并且路径较短 
			t=j; //循环过后t为下轮循环的源点 
		}
		book[t]=true; //标记做过源点 
		for(int j=1;j<=n;j++)
		dist[j]=min(dist[j],dist[t]+g[t][j]); //更新dist数组 
		}	
}
int main()
{
	memset(g,8,sizeof(g)); //将数组赋最大值  这里8不是数字8 
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c); //储存路径长度 
		}	
		dijkstra();
		for(int i=1;i<=n;i++)
		cout<<dist[i]<<" "; //输出每个点到原点的最短路 
}

灵魂画手哈哈哈哈
举个例子
第一轮dist{0，5，8，∞，∞} t=2 2为源点 刷新dist后
dist{0，5，6，8，7}
第二轮dist{0，5，6，8，7} t=3 3为源点 刷新dist
由于3号点未连接4，5 相当于跳过
第三轮dist{0，5，6，8，7} t=5 5为原点 刷新
不变
第四轮dist{0，5，6，8，7} t=4 刷新 不变
一共循环刷新4次 结束 dist里即为各个点到源点的最短路

其实这个算法背一下模板有很大帮助 现在不理解慢慢就懂了
模板

for(int i=0;i<n-1;i++) //外层循环n-1次 最后一个不需循环 
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		{
			if(!book[j]&&(t==-1||dist[j]<dist[t])) //未做过源点并且路径较短 
			t=j; //循环过后t为下轮循环的源点 
		}
		book[t]=true; //标记做过源点 
		for(int j=1;j<=n;j++)
		dist[j]=min(dist[j],dist[t]+g[t][j]); //更新dist数组 
		}