最短路径--Dijkstra

简单介绍

• 指定的一个点（源点）到其余各点的最短路径，也叫做 “单源最短路径”

讲解

• 我们可以用二维数组来存储各点间的距离信息，将没有办法直接到达的用无穷大来表示，自己到自己用0来表示，这样我们就得到了图的信息
• 初始值如下：

• 如何求最短路径呢？

1. 我们先认为1号点是选定的源点

2. 用一个一维数组dis来储存1号顶点到其余各个顶点的初始路程
   将此时dis数组中的值称为最短路程的“估计值”

3. 我们想求1号顶点到其余各个顶点的最短路程，先找一个离1号顶点最近的顶点，通过数组知道最近的顶点是2顶点，当选择了2号顶点后， dis[2]值就已经从估计值变为了确定值，即1号顶点到2号顶点的最短路程就是当前dis[2]的值，为什么呢？因为离1号顶点最近的是2号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个点的中转使1号顶点到2号顶点的路程近一步缩进了，因为1号顶点到其他顶点路程肯定没有1号顶点到2号顶点的路程近。

4. 既然选了2号顶点，接下来再看2号顶点有哪些出边？有2->3和2->4这两条边，先讨论通过2->3这条边能否让1号顶点到3号景点的路程变短，也就是说现在来比较dis[3]和dis[2]+e[2][3]的大小。其中dis [3] 表示 1 号顶点到 3号顶点的路程，dis[2]+e[2][3]表示1号顶点到2号顶点的路程，e[2][3]表示2->3这条边，所以dis[2]+e[2][3]就表示从1号顶点先到2号顶点，再通过e[2][3]这条边到达3号顶点的路程。

5. 我们发现dis[3]=12,dis[2]+e[2][3]=1+9=10,dis[3]>dis[2]+e[2][3],因此要dis[3]更新为10,这个过程有个专业的术语叫"松弛",1号顶点到3号顶点的路程即dis[3]通过按到2->3这条边松弛成功,这便是算法的主要思想，通过边来松弛1号顶点到其余各个顶点的路程。

6. 同理通过2->4，可以将dis[4]的值从∞松弛为4

7. 我们对二号顶点的所有出边进行松弛，松弛完毕后的dis数组为：
   

8. 继续在剩下的顶点（即估计值）里选一个离源点（1号顶点）最近的顶点的所有出边进行松弛

9. 将dis数组中的所有估计值变为确定值时，算法结束，最终dis数组中的值就是源点到所有顶点的最短路径

10. 可以用一个一位数组来做标记，看有哪些估计值已经变为确定值。

完整代码

#include<stdio.h>
#define MAX 999999
int main(){
	int e[10][10],i,j,k,n,m,a,t1,t2,t3,dis[10],book[10],min,u,v;
	scanf("%d %d %d",&n,&m,&a);//输入点的个数和边的条数以及源点的序号 
	//初始化数组 
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j)
				e[i][j]=0;
			else
				e[i][j]=MAX;
		}
	}
	//读入各边的距离 
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&t1,&t2,&t3);
		e[t1][t2]=t3;
	}
	//初始化dis数组 
	for(i=1;i<=n;i++)
		dis[i]=e[a][i];
	//book数组初始化 
	for(i=1;i<=n;i++)
		book[i]=0;
	book[1]=1;
	//核心语句 
	for(i=1;i<=n-1;i++){//最后一个点没有出边
		//找到离源点最近的点 
		min=MAX;
		for(j=1;j<=n;j++){
			if(book[j]==0&&dis[j]<min){
				min=dis[j];
				u=j;
			}
		} 
		book[u]=1;
		for(v=1;v<=n;v++){
			if(e[u][v]<MAX){
				if(dis[v]>dis[u]+e[u][v])
					dis[v]=dis[u]+e[u][v];
			}
		}
	}	
	
	for(i=1;i<=n;i++)
		printf("%d ",dis[i]);
	
	
	return 0;
}