迪杰斯特拉算法详解（^-^）

指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。

首先用二维数组来存储这个图， 如下：

我们还需要用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程，如下。

比如我们设俩个集合 S  ,  U， 分别代表确定值和估计值

那么一开始：

S = {1 }；

U = {2，3 ，4，5，6}；

先找一个离1号顶点最近的顶点，是2号顶点，当选择了2号顶点后，dis[2]的值就已经 从“估计值”变为了“确定值”。

S= {1， 2}；

U = {3 ， 4 ， 5 ，6 }；

接下来看2号顶点的出边，有2-3和2-4两条边。先讨论通过2-3能否让1-3号的路程变短，也就是比较dis[3]和dis[2]+e[2][3]的大小。（松弛操作）。

松弛操作其实就是指通过另外一个点作为中转点，更新这俩点之间的距离。

最终结果：S= {1 ，2 ，4 ，3， 5 ，6} // 最短路径

U = {}；

 

 

 

 

 

下面代码（超级详细）：

#include <stdio.h>
int main()
{
	int dis[10] ;//存储源点到其他顶点之间的最短距离
	int e[10][10] ;//存图存边
	int book[10];//标记确定的值
	int n , m ,t1 , t2 , t3, u , min;
	int INF = 999999;//无穷值 
	scanf("%d %d", &n, &m);//n表示顶点数， m表示边的条数
	
	//初始化
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			if(i == j)
			{
				e[i][j] = 0;
			}
			else
			{
				e[i][j] = INF;
			}
		}
	 } 
	 //读入边
	 for(int i =1 ; i <= m ; i++)
	 {
	 	scanf("%d %d %d" , &t1 ,&t2 , &t3);
	 	e[t1][t2] = t3;
	  } 
	  //初始化dis数组 ， 源点到其他顶点的初始路程 ，可直接到达就直接写该距离 ， 不能就初始为INF
	  for(int i = 1 ; i <= n ; i++)
	  {
	  	dis[i] = e[1][i];
	   } 
	   //初始化book数组
	   for(int i = 1; i <= n ;i++)
	   {
	   	book[i] = 0;
	   	book[1] = 1;
		} 
		
	//当当当~~~~ 重点来了 ， 迪杰斯特拉算法核心语句
	for(int i = 1 ; i <= n-1 ; i++)//循环dis数组  , 找最近的点 
	{
		min = INF;
		for(int j = 1 ; j <= n ; j++)//
		{
			if(book[j] == 0 && dis[j] < min)
			{
				min = dis[j];//确定最短路径通过的顶点 
				u = j;
			}
		 } 
		 book[u] = 1;//该点确定 
		 for(int v = 1 ; v <= n ; v++)//松弛操作 
		 {
		 	if(e[u][v] < INF)
		 	{
		 		if(dis[v] >dis[u] +e[u][v])
		 		{
		 			dis[v] = dis[u] + e[u][v];
				 }
			 }
		  } 
	 } 
	  for(int i = 1 ; i <= n ; i++)
		  {
		  	printf("%d " , dis[i]);
		   } 
	return 0;
 } 
 
 /*
 6 9
 1 2 1
 1 3 12
 2 3 9
 2 4 3
 3 5 5 
 4 3 4
 4 5 13
 4 6 15
 5 6 4
 */