数据结构之图的单源最短路径_图 单源最短路径

我是自动化专业的应届研究生，最终拿到了tplink、华为、vivo等公司的ssp的offer，分享自己学习过的计算机基础知识（C语言+操作系统+计算机网络+linux）以及数据结构与算法的相关知识，保证看完让你有所成长。
欢迎关注我，学习资料免费分享给你哦！还有其他超多学习资源，都是我自己学习过的，经过过滤之后的资源，免去你还在因为拥有大量资源不知如何入手的纠结，让你体系化学习。

图的单源最短路径概述

对于一个图来说，在应用之中，除了遍历，还有一种就是求取最短路径或者说求取代价最小的方式，以生活中的旅游来说，比如你在北京出发，想要去海南，有几种路径可以选择，经过上海到达或者从北京到山西到陕西到四川到云南才到达，你会怎么选择呢？如果这里的评判标准只是在路上的花费最少，那你肯定选择的是经上海到达，路费最低，这就是图的一种应用，寻找到代价最小的路径。

何谓单源？就是对于一个图来说，你指定一个初始点，求出这个初始点到整个图中的其他各点的最短路径，就是单源，就是一个起点。

无权图的单源最短路径

以上图为例，分析算法的执行过程，我们以0为起点，找到到其他各点的最短路径，因为没有各个边没有权重，所以我们可以看成权重都为1.首先是找到与0相连接的顶点1和6，到达它们的最短路径都为1.然后在从1出发，找到与1相连的顶点2和3，将其路径值置为2，然后在以顶点6为出发点，找到与顶点6相连的顶点，发现没有。

然后在以从顶点0开始的最短路径为2的顶点2来寻找，顶点4新最短路径为3。因为顶点3已经更新了，所以以顶点2为起点的时候，不在更新顶点3了。然后以顶点3为起点，顶点4和6已经更新了，只更新顶点5，路径长度为3.

然后在分别以4和5为起点，但是发现4和5为起点的时候，与他们相连的顶点都已经更新过了，不需要更新了。所以找到了以0为起点的最短路径。

其实将这个分析的过程与图的广度优先遍历是很相似的，以起点为中心，然后将与起点相连的顶点访问，然后在扩散出去，一层接一层。这样我们就可以使用一个数组来表示到达起点的最短路径的值。最开始使用一个无穷数或者-1之类的，表示还未更新，也代表着这个顶点未被访问。这样就省去了广度优先遍历visit数组来表示顶点是否被访问过。

首先以0为起点，那么它的最短路径就是0.然后将0输入队列。进入循环，只要队列不空，就一直在循环中，队列不空，说明图中的顶点没有被全部访问到。然后将0出队，寻找与0相连的顶点，判断他们是否被访问，就是判断这个顶点所在数组值是否为999，是就代表没有被访问。然后更新。并将更新顶点值的顶点入队。这次更新了1和6顶点，所以顶点1和6入队，目前队列里的值为1，6.

然后1出队，更新2和3，并且将2和3入队，目前队列里为6，2，3.

直到顶点全部出队，完成了更新，数组中的值就是从起点0到各个顶点的最短路径。

void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
{
   
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
     
    Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */
    dist[S] = 0; /* 初始化源点 */
    AddQ (Q, S);
 
    while( !IsEmpty(Q) ){
   
        V = DeleteQ(Q);
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
            if ( dist[W->AdjV]==-1 ) {
    /* 若W->AdjV未被访问过 */
                dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
                path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
                AddQ(Q, W->AdjV);
            }
    } /* while结束*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

有权图的单源最短路径

而对于有权图，就不能使用这种方法了，因为每个边的权重不一样，所以选择顶点的方法就不同了，以出发点出发，更新到与出发点相邻的顶点的权值，然后进入循环，从还未被选择的节点中，选一个到出发点距离最小的顶点A，然后访问与A相连的顶点且没被访问过的B，如果B到起始点的距离比A到起始点的距离加AB的权值大的话，说明从起始点经过A到B是最短路径，更新B到起始点的距离。直到找不到未被访问的顶点为止，结束循环，这样就把整个图中从起始点到图中各个节点的最短路径找到了。

相比较无权图的最短路径，可以用数组dist自身来判断是否是被访问过不同，有权图需要添加一个visit数组来判断是否是被访问过的，这里的访问过，是指前面所说的“从还未被选择的节点中，选一个到出发点距离最小的顶点A”。

首先初始两个数组，一个代表是否访问过，一个代表到达起始点的最短路径。

以0为起始点，标记0已经访问过了，visit[0]=1,dist[0]=0,然后根据权值更新与0相连的顶点1和6的最短路径。

然后从未被访问的1-6的顶点中选取dist值最小的顶点，为1.然后将visit[1]标记为1.现在以顶点1为出发点，更新dist数组，发现与1相连的有顶点2，dist[1]+边12的权值2是小于原来的dist[2],表示的是从起始点0到2顶点的路径中，经过顶点1到顶点2是比原来起始点0到顶点2路径短的（这也是为什么初始化时将dist初始值初始为无穷大的原因，无穷大表示从起始点0不可以到达2，现在可以经过1到达了2，当然要更新最短路径了，如果你初始化最小值，那么永远这个值都不会更新了，也就是出错了），所以更新dist[2]=dist[1]+边12权值2.

同样的道理，与1相连的顶点3，也要更新权值dist[3]=dist[1]+边13权值1.

注意更新权值并不将相应顶点标记为被访问，只有在挑选dist值最小的顶点时，才标记被访问过。因为每个边的权值不同，所以你在当前顶点更新最短路径不一定是最短的，可能从别的顶点过来的路径还存在最短的，所以不能标记。只有等到是从自己出发了，说明从其他顶点到自己的边都已经更新完了，已经可以确认目前的值是最短路径了，所以可以标记。

在从未访问节点2-6找出dist值最小的顶点3，标记为已经访问vist[3]=1，然后从3出发，与3相连的且未被访问的顶点有5和7，dist[3]+相应边的权值边34（边35）小于dist[4]（dist[5])更新权值。因为dist[3]+边36权值大于dist[6],说明经过顶点3的方式到达顶点6不是最短路径，所以不需要更新。

然后未被访问节点2，4，5，6中，选出顶点6是最小的dist，标记为访问过的。但是发现没有与6相连的顶点。

然后在2，4，5中选择dist值最小的位顶点2，标记visit[2]=1，然后访问与2相连的顶点，发现3访问过了，dist[2]+边24权值大于dist[4]所以不更新。结束。

对于顶点4和5同样的，没有可以更新的路径了，最终结束了程序，得到了如下的最短路径。

这个算法被称为Dijkstra代码如下所示：

void dijkstra(Graph graph,int d)  //d为起始点
{
   
	int *dist;
	int *visit;
	int i=0;
	Gnode tmp;
	visit=(int *)malloc(sizeof(int)*graph->Nv);
	if(visit==NULL)
	{
   
		printf("内存不足");
		return;
	}
	clear_visit(visit,graph->Nv);//将visit数组清0，实现在下面
	dist =(int *)malloc(sizeof(int)*graph->Nv);
	if(distt==NULL)
	{
   
		return;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20