迪杰特斯拉（Dijkstra）算法入门

关于这个算法我认为有以下几个重要的步骤

1.首先是将选定的点的距离设置为0
2.并设置一个标志位数组，将所有的点的初始值都设置为false，也就是没有被访问过，一旦访问过了，就会被当做纳入访问过的点的集合中
3.如何开始使用循环，对接下来的点的距离进行判定（判定条件是没有被访问过且他的距离小于当前的最小距离），从中选出最小的点，将其访问未设置为true
4.更新之后的距离，更新条件就是，当前位置到最初点的距离大于最新被标志为true的点到该点的距离加上最新被标志为true的点到最初点的距离
5.循环遍历直到结束

#include<stdio.h>
#define MAX 100
#define INF 1000000000
int map[MAX][MAX];
int dis[MAX];//距离的数组
bool mark[MAX];//记录被选中的结点 
int n;
void dijkstra(int s)//求s点到各结点的最短距离 
{
	int k;
	for(int i=0;i<n;i++)//初始化所有的结点都没有被选中 
		mark[i]=false; 
	for(int i=0;i<n;i++)//将每个结点到s结点的距离放入dis数组
		dis[i]=map[s][i];//map这个二维数组是统计两点的距离，左边是起点，右边是终点，//最后是值
	mark[s]=true;//s结点被选中 
	dis[s]=0;//将s结点的距离被设为0 
	int min;//最短距离
	for(int i=1;i<n;i++)//一共n-1次
	{
		min=INF;//找当前最小值
		for(int j=0;j<n;j++)
		{
			if(!mark[j]&&dis[j]<min)//这个是判断条件
			{
				min=dis[j];
				k=j;
			}
		}
		mark[k]=true;//k结点被选中
		for(int j=0;j<n;j++)//开始更新距离
		{
			if(!mark[j]&&(dis[j]>dis[k]+map[k][j]))
				dis[j]=dis[k]+map[k][j];
		} 
	}	
}
int main()
{
	int m,start,end;
	int a,b,c;
	printf("请分别输入顶点和边的数目:"); 
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			map[i][j]=INF;//相当于是初始化各个点的距离
	for(int i=0;i<m;i++)
	{
		printf("请输入第%d个边的起始点、终点和距离:",i+1);
		scanf("%d %d %d",&a,&b,&c);
		if(c<map[a][b]||c<map[b][a])//其实这个条件我感觉可有可无，直接赋值即可
		{
			map[a][b]=c;
			map[b][a]=c;
		}
	}
	printf("请输入源结点和目标结点:");
	scanf("%d %d",&start,&end);
	dijkstra(start);
	printf("结点%d到%d的最短路径长度为:%d\n",start,end,dis[end]);
}