图论-Dijkstra

      Dijkstra-迪杰斯特拉 算法 算法是处理单源最短路径问题常用的算法，虽然时间复杂度(n^2)较高(但是可以优化)，但是编写起来方便在处理小数据时还是很方便的.

      dijkstra 算法，在使用时需要指定一个起始点 n，因为这是 计算一个点到其它点最短路径的算法，这里需要 3 个数组 S ， U 和flag 来辅助完成，其中 S 数组用来储存 点 i 到 n 的 最短路径 即 S[i] ，U 数组来储存 还未 计算最短路径的 点 ，flag[i] 说明 点 i 已经 被计算出到n的最短路径 ，来看看过程是怎样的

      假如 有 4 个 点 A B C D 计算 A到其余三点的最短路径(如下图)

  ① 开始 S中只有A本身 ，U 中为剩余节点 S {A(0)} U {B(3),C(5),D(max)}

A(0) 表示 A 到 其本身的距离 为 0 ，D(max) 表示 D与A在一开始没有直接连接

  ② 现在 U中寻找距离A点最近的点 (这个点到A肯定是最短的了) 我们找到了B，所以 将 B加入S中 并在U中去除(用flag标记一下就OK)

这时 数组是 S{A(0),B(3) } U{C(3),D(MAX)} 然后我们再拿刚拿出的点B能直接到达的点 ：只有C 我们看到 AB + BC < AC 然后将 U 中的 C(5) 换成 C (4);

   ③ 重复 ① ② 操作；

简单介绍了过程之后看一下如何用代码实现（我代码将S 和 U合并了）：

#include<stdio.h>
#include<string.h>
#define MAXN 10000000
int maps[100][100];
int s[100];//用来存储点到原点的距离 假设 点由数字 1-100 表示 
int flag[100];//用来判断点是否计算过
void init(){  
	int i,j;
	memset(flag,-1,sizeof(int)*100);
	for (i=0;i<100;i++)
	for (j=0;j<100;j++)
	{
		if (i==j)
		maps[i][j] = 0;
		else
		maps[i][j] = MAXN;
	}

} 
void dijkstra(int x,int n){ //X 表示 起始点 ,n表示点的数量 
	int i,j,k;
	for (i=1;i<=n;i++)
	s[i] = maps[x][i];
	s[x] = 0;
	flag[x] = 1;
	for (i=1;i<=n;i++)
	{
		int min = MAXN;
		for (j=1;j<=n;j++)
		{
			if (flag[j]==-1 && min > s[j])
			{
				min = s[j]; //记录最小值 
				k = j; // 记录最小值的点 
			}
		}
		flag[k] = 1;//标记最小值的点 该点距离起始点已是最短距离
		for (j=1;j<=n;j++)
		{
			if (flag[j]!=1&&s[k]+maps[k][j] < s[j])
			{
				s[j] = min + maps[k][j];
			}
		 } 
	}
}
int main (){
	int i,n,m,a,b,c,x;//n表示点的个数 m表示边的个数，a,b 存储点 ，c存储边的权值,x为起始点 
	scanf("%d%d",&n,&m);
	init();
	for (i=0;i<m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		maps[a][b] = c;
		maps[b][a] = c;
	}
	scanf("%d",&x);
	dijkstra(x,n);
	for (i=1;i<=n;i++)
	printf("%d\n",s[i]);
}