迪杰斯特拉(Dijkstra)算法详解

发布时间:2023年12月30日

【专栏】数据结构复习之路

这篇文章来自上述专栏中的一篇文章的节选:

【数据结构复习之路】图(严蔚敏版)两万余字&超详细讲解

想了解更多图论的知识,可以去看看本专栏?

Dijkstra 算法讲解:

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是:从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。

这里我直接以书P189那个例子为基础进行讲解(附带书上的源代码)

?

先给出算法代码,然后结合着代码来讲可能会更容易理解:

/* 迪杰斯特拉(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[0] = 0;	// v0至v0路径为0
	final[0] = 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]))
			{
				dist[w] = min + G.Edge[k][w];	// 修改当前路径长度
				path[w] = k;
			}
		}
	}
}

【1】初始化(执行上述代码前面一部分)

??注意:这里的path[2] 、path[4]、path[5]没有初始化为0,主要是没必要,因为path[i] = -1,就表明 i 的前驱结点一定就是V0。

  • final[i]:标记各顶点是否已找到最短路径
  • dist[i]:最短路径长度
  • path[i]:路径上的前驱
    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[0] = 0;			// v0至v0路径为0
	final[0] = 1;			// v0至v0不需要路径

?

【2】找到距离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]))
			{
				dist[w] = min + G.Edge[k][w];	// 修改当前路径长度
				path[w] = k;
			}
		}
	}

?

【3】 重复【2】?

??【4】重复【2】

?

【5】重复【2】

?


到这里,dist[i]里面存的就是从V0到 Vi 的最短路径长度,而通过path[i] 就能找到最短路径。

这里V1至始至终都没有更新的原因是:V0根本走不到V1。

看完上述图解,那么书上P190那个表格你肯定就明了:

下图的S相当于 final[i]依次被确定为1的次序

?

?这个表格建议大家要搞懂!可能有些学校会考察画图哦

??注意:

迪杰斯特拉算法适用于求正权有向图中,源点到其余各个节点的最短路径。(图中可以有环,但不能有负权边)。

例如:如下图就不能使用迪杰斯特拉算法求节点 1 到其余各个节点的最短距离。

?

因为根据迪杰斯特拉算法,首先会更新dist[2] = 1 , final[2] = 1。由于final[2]被确定为1,即之后将不会再更新dist[2],而根据上图,显然结点1到结点2的最短路径为-1。


显然,Dijkstra 算法是基于贪心策略的。使用邻接矩阵或者带权的邻接表表示时,时间复杂度都是:O(|V|^{2})?

这里的V是图里面的结点个数。
人们可能只希望找到从源点到某个特定顶点的最短路径,但这个问题和求解源点到其他所有顶点的最短路径一样复杂,时间复杂度也为O(|V|^{2})??


?我的个人博客,欢迎访问!

文章来源:https://blog.csdn.net/m0_74215326/article/details/135306468
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。