图算法——求最短路径（Dijkstra算法）-程序员宅基地

求图的最短路径在实际生活中有许多应用，比如说在你在一个景区的某个景点，参观完后，要怎么走最少的路程到你想参观的下个景点，这就利用到了求图最短路径的算法。求图的最短路径有很多算法，这里介绍一种迪杰斯特拉（Dijkstra）算法来求图的最短路径。

在介绍算法前，需要掌握一点图的基本知识，比如说什么是路径，什么是路径长度等。如果对这些不了解的话，建议先了解一下。

这是我写的一篇博客，对图的一些基本知识的简介——图的一些基本知识。

一、什么是最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图没有边上的权值，所谓最短路径，其实指的就是两个顶点之间经过的边数最少的路劲（即可以理解为把每一条边的权值看作是1）。

对于网图来说，最短路径，是指两顶点之间经过的边上的权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

求带权有向图G的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一个顶点到其它顶点的最短路径，可以通过经典的 Dijkstra（迪杰斯特拉）算法求解（即是我要介绍的算法）；二是求每对顶点间的最短路径，可通过Floyd（弗洛伊德）算法来求解。

二、迪杰斯特拉（Dijkstra）算法

Dijkstra算法算法思路是设置一个集合S记录已求得的最短路径的顶点，初始时把源点V0（图中的某个顶点）放入S，集合S每并入一个新顶点 V $_{i}$ ，都要修改源点V0到集合 V-S 中顶点当前的最短路径长度值（这里可能大家会很懵，但等会我会用一个例子来解说）。

在构造过程中需要两个辅助数组：

dist[ ] ：记录从源点V0到其他各顶点当前的最短路径长度，它的初态为：若从 V0 到 V $_{i}$ 有直接路径（即V0 和 V $_{i}$ 邻接），则dist[ i ]为这两个顶点边上的权值；否则置 dist[ i ] 为 ∞。
path[ ]：path[ i ]表示从源点到顶点 i 之间的最短路径的前驱结点。在算法结束时，可以根据其值追溯到源点 V0 到 V $_{i}$ 的最短路径。

假设从顶点 V0 = 0出发，邻接矩阵Edge表示带权无向图，Edge[i][j]表示无向边 (i, j)的权值，若不存在无向边(i, j)，则Edge[i][]为 ∞。

Dijkstra算法步骤如下：

1）初始化：集合S初始化为{0}，dist[ ] 的初始值dist[i] = Edge[0][i]，path[ ]的初始值path[i] = -1，i = 1,2,...,n-1。

2）从顶点集合 V - S中选出V $_{j}$ ，满足dist[j] = Min{dist[i] | V $_{i}$ $\in$ V - S}，V $_{j}$ 就是当前求的一条从 V0 出发的最短路径的终点，令S = S $\cup$ {j}。

3）修改从V0出发到集合 V - S上任一顶点 V $_{k}$ 可达的最短路径长度：若

dist[j] + Edge[j][k] < dist[k]，则更新 dist[k] = dist[j] + Edge[j][k]，并修改path[k] = j（即修改顶点V $_{k}$ 的最短路径的前驱结点）。

4）重复 2）~ 3）操作共 n-1 次，直到所有的顶点都包含在 S 中。

解释下步骤3），每当一个顶点加入S后，可能需要修改源点V0 到集合 V-S中的可达顶点当前的最短路径长度。下面举一个例子。如下图所示，源点为V0，初始时S = {V0}，dist[1] = 6, dist[2] = 3,当V $_{2}$ 并入集合S后，dist[1] 需要更新为 5（其比6小，即说明两点之间不是直线最短，要根据两点之间路径的权值之和来看）。

下面来讲解利用Dijkstra算法来求下图中的顶点 0 出发至其余顶点的最短路径的过程。

初始化：集合S初始化为{V $_{0}$ }，V $_{0}$ 可达V $_{1}$ 和V $_{2}$ ，其余顶点不可达，因此dist[]数组和path[]数组的设置如下：

第一轮：选出最小dist[2]，将顶点 V $_{2}$ 并入集合S，此时已找到 V $_{0}$ 到 V $_{2}$ 的最短路径，S = {V $_{0}$ ，V $_{2}$ }。当 V $_{2}$ 加入到S后，从V $_{0}$ 到集合V-S中可到达顶点的最短路径长度可能会产生变化。因此需要更新dist[]数组。V $_{2}$ 可达V $_{1}$ ，因V $_{0}$ -> V $_{2}$ -> V $_{1}$ 的距离 5 比 dist[1] = 6小，更新dist[1] = 5，并修改 path[1] = 2（即V $_{1}$ 的最短路径的前驱为V $_{2}$ ）；V $_{2}$ 可达 V $_{3}$ ，V $^{0}$ -> V $_{2}$ - > V $_{3}$ 的距离 8 比 dist[3] = ∞ 小，更新dist[3] = 8，path[3] = 2；V $_{2}$ 可达V $_{5}$ ，V $^{0}$ -> V $_{2}$ -> V $_{5}$ 的距离 10 小于 dist[5] = ∞，更新dist[5] = 10，path[5] = 2。V $_{2}$ 再无到达其余的顶点的路径，结束这一轮，此时dist[]数组和path[]数组如下：

第二轮：选出最小值dist[1]，将顶点 V $_{1}$ 并入集合S，此时已找到 V $_{0}$ 到 V $_{1}$ 的最短路径，S = {V $_{0}$ ,V $_{2}$ ，V $_{1}$ }。然后更新dist[]数组和path[]数组，V $_{1}$ 可达V $_{3}$ ，V $_{0}$ -> V $_{2}$ -> V $_{1}$ -> V $_{3}$ 的距离 6 小于 dist [3] = 8 ，更新 dist[3] = 6，path[3] = 1；V $_{1}$ 可达 V $_{2}$ ，但V $_{2}$ 已经在集合S中，故不进行操作；V $_{1}$ 可达 V $_{4}$ ， V $_{0}$ -> V $_{2}$ -> V $_{1}$ -> V $_{4}$ 的距离 9 小于 dist[4] = ∞，更新dist[4] = 9，path[4] = 1。V $_{1}$ 已无到达其余顶点的路径，结束此轮，此时dist[]数组和path[]数组如下：

第三轮：选出最小值 dist[3]，将顶点 V $_{3}$ 并入集合 S，此时已找到 V $_{0}$ 到 V $_{3}$ 的最短路径，S = { V $_{0}$ ,V $_{2}$ ，V $_{1}$ ，V $_{3}$ }。接着更新dist[]数组和path[]数组，V $_{3}$ 可到达 V $_{4}$ ， V $_{0}$ -> V $_{2}$ -> V $_{1}$ -> V $_{3}$ -> V $_{4}$ 的距离为 9 等于 dist[4] = 9，我们不做更新；V $_{3}$ 可到达 V $_{5}$ ， V $_{0}$ -> V $_{2}$ -> V $_{1}$ -> V $_{3}$ -> V $_{5}$ 的距离为 12 大于 dist[5] = 10，不做更新。 V $_{3}$ 再无达到其余顶点的路径，结束此轮，此时dist[]数组和path[]数组如下：

第四轮：选出最小值 dist[4]，将顶点 V $_{4}$ 并入集合 S，此时已找到 V $_{0}$ 到 V $_{4}$ 的最短路径，S = { V $_{0}$ ,V $_{2}$ ，V $_{1}$ ，V $_{3}$ ，V $_{4}$ }。继续更新dist[]数组和path[]数组，V $_{4}$ 可到 V $_{5}$ ， V $_{0}$ -> V $_{2}$ -> V $_{1}$ -> V $_{4}$ -> V $_{5}$ 的距离 11 小于 dist[5] = 10，故不进行更新操作；V $_{4}$ 可到 V $_{6}$ ， V $_{0}$ -> V $_{2}$ -> V $_{1}$ -> V $_{4}$ -> V $_{6}$ 的距离 11 小于 dist[6] = ∞，更新 dist[6] = 11，path[6] = 4。V $_{4}$ 再无达到其余顶点的路径，结束此轮，此时dist[]数组和path[]数组如下：

第五轮：选出最小值 dist[5]，将顶点 V $_{5}$ 并入集合S，此时已找到 V $_{0}$ 到 V $_{5}$ 的最短路径，S = { V $_{0}$ ,V $_{2}$ ，V $_{1}$ ，V $_{3}$ ，V $_{4}$ ，V $_{5}$ }。然后ist[]数组和path[]数组，V $_{}$ $_{5}$ 可到 V $_{6}$ ， V $^{0}$ -> V $_{2}$ -> V $_{5}$ -> V $_{6}$ 的最短路径 13 大于 dist[6]，故不进行更新操作。V $_{6}$ 再无达到其余顶点的路径，结束此轮，此时dist[]数组和path[]数组如下：

第六轮：选出最小值 dist[6]，将顶点 V $_{6}$ 并入集合，此时全部顶点都已包含在S中，结束算法。

整个算法每一轮的结果如下：

总结：Dijkstra算法就是最开始选离源点V $_{0}$ 最近的点，然后选好点后，再从选好点的看其邻接点的距离dist[]是否减小，减小就修改dist[]和path[]；否则就不进行修改操作。Dijkstra算法基于贪心策略，用邻接矩阵表示图时，来使用Dijkstra算法，其时间复杂度为O(n*n)。当边上带有负权值时，Dijkstra算法并不适用。

使用dist[]数组和path[]数组，求最短路径，这里介绍一个例子，其它顶点依次类推。

V $_{0}$ 到V $_{6}$ 的最短路径，先利用dist[6] = 11 得出 V $_{0}$ 到V $_{6}$ 的距离，然后利用path[]得出路径。path[6] = 4，顶点V $_{6}$ 的前驱顶点是 V $_{4}$ ，再由 path[4] = 1,表示 V $_{4}$ 的前驱是 V $_{1}$ , path[1] = 2，表示 V $_{1}$ 的前驱是 V $_{2}$ ，path[2] = -1，结束。最后可以得到 V $_{0}$ 到 V $_{6}$ 的最短路径为 V $_{6}$ <- V $_{4}$ <- V $_{1}$ <- V $_{2}$ <- V $_{0}$ ，即 V $_{0}$ -> V $_{2}$ -> V $_{1}$ -> V $_{4}$ -> V $_{6}$ 。

三、应用Dijkstra算法

理解上面的Dijkstra算法求最短路径的过程，那么下面的应用Dijkstra算法的程序就很容易理解。此程序分三大块，在程序末尾我会来粗略介绍下。

使用此程序需输入以下内容创建图G：

第一步：7 12

第二步：0123456

第三步：依次输入下面的内容，输入完一行就按下换行键

0 1 6

0 2 3

1 2 2

1 3 1

1 4 4

2 3 5

2 5 7

3 4 3

3 5 6

4 5 2

4 6 2

5 6 3

上面输入完后，即可创建下面的图G：

/*
使用此程序需输入以下内容创建图G：
第一步：7 12
第二步：0123456
第三步：依次输入下面的内容，输入完一行就按下换行键
0 1 6
0 2 3
1 2 2
1 3 1
1 4 4
2 3 5
2 5 7
3 4 3
3 5 6
4 5 2
4 6 2
5 6 3
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MaxVerterNum 100		// 顶点数目的最大值
#define INFINITY 65535			// 用65535代表 ∞

typedef char VertexType;		// 顶点的数据类型
typedef int EdgeType;			// 带权图中边上权值的数据类型

/* 邻接矩阵的存储结构 */
typedef struct
{
	VertexType Vexs[MaxVerterNum];					// 顶点表
	EdgeType Edge[MaxVerterNum][MaxVerterNum];		// 邻接矩阵
	int vexNum, arcNum;								// 图当前顶点数和弧数
}MGraph;

/*清除缓冲区的换行符*/
void Clean(void)
{
	while (getchar() != '\n')
		continue;
}

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G);

/* 迪杰斯特拉（Dijkstra) 算法*/
typedef int Patharc[MaxVerterNum];			// 用于存储最短路径下标的数组，从源点Vi到顶点Vj之间的最短路径的前驱
typedef int ShortPathTable[MaxVerterNum];	// 用于存储到各点最短路径的权值和
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc path, ShortPathTable D);

/* 输出最短路径 */
/* Dijkstra算法的结果输出 */
void Show_ShortestPath_Dijkstra(Patharc path, ShortPathTable dist, MGraph G, int v0);

int main(void)
{
	MGraph G;
	Patharc path;
	ShortPathTable dist;
	CreateMGraph(&G);
	for (int i = 0; i < G.vexNum; i++) // 输出各点到各点的最短路径序列，不再局限于一个顶点
	{
		ShortestPath_Dijkstra(G, i, path, dist);
		Show_ShortestPath_Dijkstra(path, dist, G, i);
	}
	return 0;
}

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{
	int i, j, k, w;
	printf("请输入顶点数和边数：");
	scanf("%d %d", &G->vexNum, &G->arcNum);			// 获取无向图顶点数和边数
	printf("请输入全部顶点信息：\n");
	Clean();									    // 将换行符去除
	for (i = 0; i < G->vexNum; i++)					// 读取顶点信息，建立顶点表
		scanf("%c", &G->Vexs[i]);
	for (i = 0; i < G->vexNum; i++)
		for (j = 0; j < G->vexNum; j++)
			G->Edge[i][j] = INFINITY;				// 邻接矩阵初始化
	for (k = 0; k < G->arcNum; k++)					// 读入arcNum条边，建立邻接矩阵
	{
		printf("请输入边（Vi, Vj)上的下标i，下标j和权w：\n");
		scanf("%d %d %d", &i, &j, &w);				// 获取边和权
		G->Edge[i][j] = w;							// 无向图矩阵对称
		G->Edge[j][i] = G->Edge[i][j];
	}
	return;
}

/* 迪杰斯特拉（Dijkstra) 算法*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc path, ShortPathTable dist)
{
	int v, w, k, min;
	int final[MaxVerterNum];				/* final[w] = 1表示求得顶点 v0 至 vw的最短路                    径，即已访问过顶点vw*/
	for (v = 0; v < G.vexNum; v++)
	{
		final[v] = 0;						// 全部顶点初始化为未知最短路径状态
		dist[v] = G.Edge[v0][v];			// 将与v0点有连线的顶点加上权值
		path[v] = -1;						// 初始化路劲数组p为-1
	}
	dist[v0] = 0;							// v0至v0路径为0
	final[v0] = 1;							// v0至v0不需要路径
	/* 开始主循环，每次求得v0到某个顶点v的最短路径*/
	for (v = 1; v < G.vexNum; v++)
	{
		min = INFINITY;						// 当前所知离v0顶点的最近距离
		for (w = 0; w < G.vexNum; w++)		// 寻找离v0最近的顶点
		{
			if (!final[w] && dist[w] < min)
			{
				k = w;
				min = dist[w];				// w顶点离v0顶点更近
			}
		}
		final[k] = 1;						// 将目前找到的最近的顶点置为1
		for (w = 0; w < G.vexNum; w++)		// 修正当前最短路径及距离
		{
			/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
			if (!final[w] && (min + G.Edge[k][w] < dist[w]))
			{
				/* 找到了更短的路径，修改D[w]和P[w] */
				dist[w] = min + G.Edge[k][w];	// 修改当前路径长度
				path[w] = k;
			}
		}
	}
}

/* 输出最短路径 */
/* Dijkstra算法的结果输出 */
void Show_ShortestPath_Dijkstra(Patharc path, ShortPathTable dist, MGraph G, int v)
{
	int w, k;
	printf("V%d到各点的最短路径如下：\n", v);
	for (w = 0; w < G.vexNum; w++)
	{
		if (w != v)
		{
			printf("V%d-V%d weight: %d", v, w, dist[w]);
			k = path[w];
			printf(" path: V%d", w);
			while (k != -1)  // 当 k = -1 ，结束循环并输出源点
			{
				printf(" <- V%d", k);
				k = path[k];
			}
			printf(" <- V%d\n", v);
		}
	}
	printf("\n");
}

（1） Dijkstra算法函数分析

/* 迪杰斯特拉（Dijkstra) 算法*/
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc path, ShortPathTable dist)
{
	int v, w, k, min;
	int final[MaxVerterNum];				// final[w] = 1表示求得顶点 v0 至 vw的最短路径，即已访问过顶点vw
	for (v = 0; v < G.vexNum; v++)
	{
		final[v] = 0;						// 全部顶点初始化为未知最短路径状态
		dist[v] = G.Edge[v0][v];			// 将与v0点有连线的顶点加上权值
		path[v] = -1;						// 初始化路劲数组p为-1
	}
	dist[v0] = 0;							// v0至v0路径为0
	final[v0] = 1;							// v0至v0不需要路径
	/* 开始主循环，每次求得v0到某个顶点v的最短路径*/
	for (v = 1; v < G.vexNum; v++)
	{
		min = INFINITY;						// 当前所知离v0顶点的最近距离
		for (w = 0; w < G.vexNum; w++)		// 寻找离v0最近的顶点
		{
			if (!final[w] && dist[w] < min)
			{
				k = w;
				min = dist[w];				// w顶点离v0顶点更近
			}
		}
		final[k] = 1;						// 将目前找到的最近的顶点置为1
		for (w = 0; w < G.vexNum; w++)		// 修正当前最短路径及距离
		{
			/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
			if (!final[w] && (min + G.Edge[k][w] < dist[w]))
			{
				/* 找到了更短的路径，修改D[w]和P[w] */
				dist[w] = min + G.Edge[k][w];	// 修改当前路径长度
				path[w] = k;
			}
		}
	}
}

上面数组final[]保存已有路径的结点，有最短路径的结点的值为 1，无最短路径的结点的值为 0，path[]数组记录结点 V $_{i}$ 的前驱结点，dist[]数组，记录结点 V $_{i}$ 的前驱结点。

首先进行初始化，final[]数组的元素的值均为 0，path[]数组的值均为 -1,当path[i]=-1时，说明此结点的前驱结点即是源点V $_{0}$ ，dist[]的元素值初始化为源点V $_{0}$ 到邻接点的距离。

接着进入for循环，for循环内的第一个for循环用于找到 dist[] 数组的最小值。

for循环内的第二个for循环用于进行修正。

以上便是Dijkstra算法函数的基本内容。三大块——初始化，找dist[]最小元素、修正路径。

人生是一场无休、无歇、无情的战斗，凡是要做个够得上称为人的人，都得时时向无形的敌人作战。 ——罗曼·罗兰

以此句献给看这篇博客的每一个人。

本文链接：https://blog.csdn.net/qq_61959780/article/details/127983035

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

settext 下划线_Android TextView 添加下划线的几种方式-程序员宅基地

文章浏览阅读748次。总结起来大概有5种做法：将要处理的文字写到一个资源文件，如string.xml(使用html用法格式化)当文字中出现URL、E-mail、电话号码等的时候，可以将TextView的android:autoLink属性设置为相应的的值，如果是所有的类型都出来就是**android:autoLink="all"，当然也可以在java代码里做,textView01.setAutoLinkMask(Li..._qaction::settext 无法添加下划线

TableStore时序数据存储 - 架构篇_tablestore 时间类型处理-程序员宅基地

文章浏览阅读6.3k次，点赞2次，收藏10次。摘要：背景随着近几年物联网的发展，时序数据迎来了一个不小的爆发。从DB-Engines上近两年的数据库类型增长趋势来看，时序数据库的增长是非常迅猛的。在去年我花了比较长的时间去了解了一些开源时序数据库，写了一个系列的文章（综述、HBase系、Cassandra系、InfluxDB、Prometheus），感兴趣的可以浏览。背景随着近几年物联网的发展，时序数据迎来了一个不小的爆发。从DB..._tablestore 时间类型处理

Ubuntu20.04下成功运行VINS-mono_uabntu20.04安装vins-mono-程序员宅基地

文章浏览阅读5.7k次，点赞8次，收藏49次。可以编译成功但是运行时段错误查找原因应该是ROS noetic版本中自带的OpenCV4和VINS-mono中需要使用的OpenCV3冲突的问题。为了便于查找问题，我只先编译feature_tracker包。解决思路历程：o想着把OpenCV4相关的库移除掉，但是发现编译feature_tracker的时候仍然会关联到Opencv4的库，查找原因是因为cv_bridge是依赖opencv4的，这样导致同时使用了opencv3和opencv4,因此运行出现段错误。oo进一步想着（1）把vins-mon_uabntu20.04安装vins-mono

TMS320C6748_EMIF时钟配置_tms 6748-程序员宅基地

文章浏览阅读3.6k次，点赞3次，收藏12次。创龙TL6748开发板中，EMIFA模块使用默认的PLL0_SYSCLK3时钟，使用AISgen for D800K008工具加载C6748配置文件C6748AISgen_456M_config（Configuration files，在TL_TMS6748/images文件夹下），由图可以看到DIV3等于4，注意这里的DIV3就是实际的分频值（x），而不是写入相应PLL寄存器的值（x-1）。_tms 6748

eigen稀疏矩阵拼接（基于块操作的二维拼接）的思考-程序员宅基地

文章浏览阅读5.9k次，点赞4次，收藏13次。转载请说明出处：eigen稀疏矩阵拼接（块操作）eigen稀疏矩阵拼接（块操作）关于稀疏矩阵的块操作：参考官方链接 However, for performance reasons, writing to a sub-sparse-matrix is much more limited, and currently only contiguous sets of columns..._稀疏矩阵拼接

基于Capon和信号子空间的变形算法实现波束形成附matlab代码-程序员宅基地

文章浏览阅读946次，点赞19次，收藏19次。波束形成是天线阵列信号处理中的一项关键技术，它通过对来自不同方向的信号进行加权求和，来增强特定方向的信号并抑制其他方向的干扰。本文介绍了两种基于 Capon 和信号子空间的变形算法，即最小方差无失真响应 (MVDR) 算法和最小范数算法，用于实现波束形成。这些算法通过优化波束形成权重向量，来最小化波束形成输出的方差或范数，从而提高波束形成性能。引言波束形成在雷达、声纳、通信和医学成像等众多应用中至关重要。它可以增强目标信号，抑制干扰和噪声，提高系统性能。