devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构与算法（7-4）最短路径（迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法）_数据结果 最短路径

作者：繁依Fanyi0 | 2024-07-13 23:34:33

赞

踩

数据结果 最短路径

目录

一、最短路径概念

二、迪杰斯特拉(Dijkstra)算法（单源最短路径）

1、原理

2、过程

 3、代码

三、弗洛伊德(Floyd)算法（多源最短路径）

1、原理

2、存储

3、遍历

4、代码

参考资料

 

一、最短路径概念

最短路径，顾名思义，两结点之间最短的路径（可以是非邻接结点）。

最小生成树和最短路径区别：

最小生成树：连通图的最短路径。

最短路径：两任意结点之间（可以非邻接）的最短路径。

二、迪杰斯特拉(Dijkstra)算法（单源最短路径）

优点：效率较高，时间复杂度为O(n^2)。

缺点：只能求一个顶点到所有顶点的最短路径。 （单源最短路）

1、原理

1、先选定一个根结点，并选定一个数组，先确定未遍历前的初始距离，把距离最短的邻接结点选定为中间结点，并标记访问过，开始往下遍历，挨个访问那个中间结点的邻接结点。计算出根结点到中间结点+中间结点到新邻接结点的距离，作为新距离，对比新距离和旧距离，如果新距离大，则把新距离替换掉旧距离，否则不变。

2、一轮访问结束后，从未标记的结点中选定距离最短的，把它作为中间结点，继续往下访问。若都标记过，则算法结束。

2、过程

 1、保存根结点及到其他结点的权（距离）

 2、 访问最近结点作为中间结点

3、对比新距离（根结点到中间结点+中间结点到新结点）和旧距离（根结点直接到新结点） 

 4、若新距离短，修改保存到数组

 5、继续访问后面的，把未访问的距离根最近结点作为中间结点，继续访问它的邻接结点

 6、继续对比新距离和旧距离

 7、若新距离短，则修改保存到数组

 8、 继续以距离根结点最短的结点为对象，访问它的邻接结点

 9、全部访问完毕，结束算法

欣赏一下自己的稿书： 

 3、代码

  1. //迪杰斯特拉(Dijkstra)算法
  2. /*测试案例
  3. ABCDEFGHI
  4. B 1 C 5
  5. A 1 C 3 D 7 E 5
  6. A 5 B 3 E 1 F 7
  7. B 7 E 2 G 3
  8. B 5 C 1 F 3 H 9 G 6 D 2
  9. C 7 E 3 H 5
  10. D 3 E 6 H 2 I 7
  11. F 5 E 9 G 2 I 4
  12. G 7 H 4
  13. */
  14. #define _CRT_SECURE_NO_WARNINGS
  15. #include<stdio.h>
  16.  
  17. #define MAXSIZE 20
  18. #define MAX 65535					//代表无穷大
  19. int length = 0;							//顶点个数
  20. int root = 0;								//根顶点
  21. int rootDist[MAXSIZE];				//根顶点（记录根到其他顶点的距离）
  22. bool visit[MAXSIZE];				//记录各结点是否访问
  23.  
  24.  
  25. //图（顶点和权）
  26. typedef struct
  27. {
  28. 	char vertex[MAXSIZE];
  29. 	int weight[MAXSIZE][MAXSIZE];			//权可以代替边（自身为0，相连有值，不相连无穷大）
  30. }Graph;
  31. Graph G;
  32.  
  33.  
  34. //输入顶点
  35. void InputVertex()
  36. {
  37. 	int i;
  38. 	char ch;
  39. 	printf("请输入图的顶点：\n");
  40. 	scanf("%c", &ch);
  41. 	for (i = 0; i < MAXSIZE && ch != '\n'; i++)
  42. 	{
  43. 		G.vertex[i] = ch;
  44. 		scanf("%c", &ch);
  45. 	}
  46. 	length = i;
  47. }
  48.  
  49. //图权重初始化
  50. void GraphWeightInit()
  51. {
  52. 	int i, j;
  53. 	for (i = 0; i < length; i++)
  54. 	{
  55. 		for (j = 0; j < length; j++)
  56. 		{
  57. 			if (i == j)							//指向自己
  58. 				G.weight[i][j] = 0;
  59. 			else
  60. 				G.weight[i][j] = MAX;	//无穷大
  61. 		}
  62. 	}
  63. }
  64.  
  65. //根据数据查找图顶点下标
  66. int FindIndex(char ch)
  67. {
  68. 	int i;
  69. 	for (i = 0; i < length; i++)
  70. 	{
  71. 		if (G.vertex[i] == ch)
  72. 			return i;
  73. 	}
  74. 	return -1;
  75. }
  76.  
  77. //创建图
  78. void CreateGraph()
  79. {
  80. 	int i, j, index, weight;
  81. 	char ch;
  82. 	for (i = 0; i < length; i++)
  83. 	{
  84. 		printf("请输入%c的邻接顶点及权重（空格分隔，换行结束）：\n", G.vertex[i]);
  85. 		scanf("%c", &ch);
  86. 		while (ch != '\n')
  87. 		{
  88. 			while (ch == ' ')				//为空格
  89. 			{
  90. 				scanf("%c", &ch);			//输入字符
  91. 				continue;
  92. 			}
  93. 			index = FindIndex(ch);
  94. 			scanf("%d", &weight);		//输入权重
  95. 			while (weight == 32)		//32为空格的ASCII码
  96. 			{
  97. 				scanf("%d", &weight);
  98. 				continue;
  99. 			}
  100. 			G.weight[i][index] = weight;	//存入权重
  101. 			scanf("%c", &ch);				//(下一轮)输入字符
  102. 		}
  103. 	}
  104. }
  105.  
  106. //根结点初始化
  107. void Init()
  108. {
  109. 	int i;
  110. 	printf("请输入根结点：\t");
  111. 	scanf("%d", &root);
  112. 	for (i = 0; i < length; i++)
  113. 	{
  114. 		rootDist[i] = G.weight[root][i];		//把0作为根，初始化
  115. 		visit[i] = false;								//未访问
  116. 	}
  117. }
  118.  
  119. //取最小（在未访问的结点中）
  120. int GetMinInVisit()
  121. {
  122. 	int i, min = 0;
  123. 	for (i = 0; i < length; i++)
  124. 	{
  125. 		//未访问
  126. 		if (!visit[i])
  127. 		{
  128. 			//找到最小下标（不能是自身）
  129. 			if (rootDist[min] > rootDist[i] || rootDist[min] == 0)
  130. 			{
  131. 				min = i;
  132. 			}
  133. 		}
  134. 	}
  135. 	return min;
  136. }
  137.  
  138. //检查是否访问完毕
  139. bool IsNull()
  140. {
  141. 	bool flag = true;
  142. 	for (int i = 0; i < length; i++)
  143. 	{
  144. 		if (!visit[i])				//还有未访问的
  145. 			flag = false;
  146. 	}
  147. 	return flag;
  148. }
  149.  
  150. //迪杰斯特拉(Dikstra)算法（生成根到其他顶点的最短路径）
  151. void Dijkstra(int index)
  152. {
  153. 	int i;
  154. 	visit[index] = true;						//标记访问
  155. 	printf("%c %d\t", G.vertex[index], rootDist[index]);
  156.  
  157. 	//遍历中间结点的邻接结点，对比新旧距离
  158. 	for (i = 0; i < length; i++)
  159. 	{
  160. 		//若 旧距离 > 新距离（改变新距离覆盖旧距离）
  161. 		if (rootDist[i] > (rootDist[index] + G.weight[index][i]))
  162. 		{
  163. 			rootDist[i] = rootDist[index] + G.weight[index][i];
  164. 		}
  165. 	}
  166.  
  167. 	//退出判断
  168. 	if (IsNull())
  169. 		return;
  170. 	index = GetMinInVisit();				//取出最小邻接结点，作为中间结点
  171. 	Dijkstra(index);								//递归调用Dijkstra()
  172. }
  173.  
  174. //输出测试
  175. void Print()
  176. {
  177. 	for (int i = 0; i < length; i++)
  178. 	{
  179. 		printf("\n%c结点邻接结点：\t", G.vertex[i]);
  180. 		for (int j = 0; j < length; j++)
  181. 		{
  182. 			if (G.weight[i][j] != 0 && G.weight[i][j] != MAX)		//有邻接结点
  183. 			{
  184. 				printf("%c %d\t", G.vertex[j], G.weight[i][j]);
  185. 			}
  186. 		}
  187. 	}
  188. }
  189.  
  190. int main()
  191. {
  192. 	InputVertex();				//输入顶点
  193.  
  194. 	GraphWeightInit();		    //图权重初始化
  195.  
  196. 	CreateGraph();				//创建图
  197.  
  198. 	Init();						//初始化
  199.  
  200. 	Dijkstra(root);				//迪杰斯特拉算法（先以根结点为中间结点遍历）（生成根到其他顶点的最短路径）
  201.  
  202. 	//Print();					//测试输出
  203.  
  204. 	return 0;
  205. }

三、弗洛伊德(Floyd)算法（多源最短路径）

优点：求所有顶点到所有顶点的最短路径。（多源最短路）

缺点：效率较低，时间复杂度为O(n^3)。  

1、原理

基本思想：

不断找点进行中转，比较中转前后的最小距离。

原理：

最优子结构：图结构中一个显而易见的定理：最短路径的子路径仍然是最短路径 ,这个定理显而易见，比如一条从a到e的最短路径a->b->c->d->e 那么 a->b->c 一定是a到c的最短路径，c->d->e一定是c到e的最短路径，反过来，（原理）如果一条最短路必须要经过点k，那么i->k的最短路径+k->j的最短路径一定是i->j 经过k的最短路径，因此，最优子结构可以保证。

（左边矩阵是改进前的，右边矩阵是改进后的。）

弗洛伊德算法定义了两个二维矩阵：

D矩阵存放最小权(最短路径)，P矩阵存放最短前驱(中转点)

1、矩阵D记录顶点间的最小路径
例如D[1][2]= 3，说明顶点1 到 2 的最短路径为3；
2、矩阵P记录顶点间最小路径中的中转点
例如P[1][2]= 0 说明，1 到 2的最短路径轨迹为：1 -> 0 -> 2。
它通过3重循环，medium为中转点，begin为起点，end为终点，循环比较D[begin][end] 和 D[begin][medium] + D[medium][end] 之间的最小值，如果(D[begin][medium] + D[medium][end] )为更小值，则把(D[begin][medium] + D[medium][end] )覆盖保存在(D[begin][end])中。

2、存储

弗洛伊德算法定义了两个二维矩阵：

D矩阵存放最小权(最短路径)，P矩阵存放最短前驱(中转点)

 思考：如果求任意两点之间的最短路径，两点之间可以直接到达但却不是最短的路径，要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点medium），并通过这个顶点medium中转即a->medium->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转顶点medium是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多中转点会更短。

下面给出一些例子深入理解一下：

例：        4 -> 3          一、直接：D[4][3] = 12       二、 过1：D[4][1]+D[1][3]=11   

过1更短，        则D[4][3] = 11        且P[4][3] = P[4][1] = 1

例：        1 ->3         一、直接：D[1][3] = 6        二、过2：D[1][2]+D[2][3] = 5

过2更短，        则D[1][3] = 6          且P[1][3] = P[1][2] = 2

 1、假如现在只允许经过1号顶点，求任意两点的最短路径我们应该怎么求呢？？

 我们只需要判断 (D[begin][end]) 与 (D[begin][1] + D[1][end]) 的大小。（前者直接到达，后者经历中转）

  1. //只经过1号中转顶点
  2. for (begin = 1; begin <= n; begin++)
  3.     for (end = 1; end <= n; end++)
  4.         if (D[begin][end] > D[begin][1] + D[1][end])
  5.             D[begin][end] = D[begin][1] + D[1][end];

 在只允许经过1号中转顶点的情况下，任意两点之间的路程更新为：

2、继续求在只允许经过1和2号两个中转顶点的情况下任意两点之间的最短路程

  1. //只经过1号中转顶点
  2. for (begin = 1; begin <= n; begin++)
  3.     for (end = 1; end <= n; end++)
  4.         if (D[begin][end] > D[begin][1] + D[1][end])
  5.             D[begin][end] = D[begin][1] + D[1][end];
  6.  
  7.  
  8. //只经过2号中转顶点
  9. for (begin = 1; begin <= n; begin++)
  10.     for (end = 1; end <= n; end++)
  11.         if (D[begin][end] > D[begin][2] + D[2][end])
  12.             D[begin][end] = D[begin][2] + D[2][end];

在只允许更新1号和2号顶点的情况下，任意两点之间的路径更新为：

 3、..........继续往后，运行经过n个中转顶点（即全部）

  1. //运行经过所有中转顶点
  2. for(medium = 0; medium <= n; medium++)
  3.     for (begin = 1; begin <= n; begin++)
  4.         for (end = 1; end <= n; end++)
  5.             if (D[begin][end] > D[begin][medium] + D[medium][end])
  6.                 D[begin][end] = D[begin][medium] + D[medium][end];

允许经过所有中转顶点，最后的两点路径更新： 

3、遍历

  1. //遍历弗洛伊德算法
  2. //确定begin -> end：从最近的前驱开始，一点一点往后追溯
  3. void Traverse_Floyd()
  4. {
  5. 	int medium = 0;
  6. 	for (int begin = 0; begin < length; begin++)
  7. 	{
  8. 		for (int end = 0; end < length; end++)
  9. 		{
  10. 			printf("\n%c", G.vertex[begin]);
  11. 			medium = P[begin][end];                     //开始追溯（此为最近的前驱）
  12. 			while (medium != end)						//未追溯到尾
  13. 			{
  14. 				printf("->%c", G.vertex[medium]);		//打印中间结点
  15. 				medium = P[medium][end];				//向后追溯
  16. 			}
  17. 		}
  18. 	}
  19. }

4、代码

  1. //弗洛伊德(Floyd)算法
  2. /*测试案例
  3. ABCDEFGHI
  4. B 1 C 5
  5. A 1 C 3 D 7 E 5
  6. A 5 B 3 E 1 F 7
  7. B 7 E 2 G 3
  8. B 5 C 1 F 3 H 9 G 6 D 2
  9. C 7 E 3 H 5
  10. D 3 E 6 H 2 I 7
  11. F 5 E 9 G 2 I 4
  12. G 7 H 4
  13. */
  14. #define _CRT_SECURE_NO_WARNINGS
  15. #include<stdio.h>
  16.  
  17. #define MAXSIZE 20
  18. #define MAX 65535							//代表无穷大
  19. int length = 0;									//顶点个数
  20. int D[MAXSIZE][MAXSIZE];		//存放顶点之间的权
  21. int P[MAXSIZE][MAXSIZE];		//存放顶点之间的前驱（中间结点）
  22.  
  23. //图（顶点和权）
  24. typedef struct
  25. {
  26. 	char vertex[MAXSIZE];
  27. 	int weight[MAXSIZE][MAXSIZE];			//权可以代替边（自身为0，相连有值，不相连无穷大）
  28. }Graph;
  29. Graph G;
  30.  
  31.  
  32. //输入顶点
  33. void InputVertex()
  34. {
  35. 	int i;
  36. 	char ch;
  37. 	printf("请输入图的顶点：\n");
  38. 	scanf("%c", &ch);
  39. 	for (i = 0; i < MAXSIZE && ch != '\n'; i++)
  40. 	{
  41. 		G.vertex[i] = ch;
  42. 		scanf("%c", &ch);
  43. 	}
  44. 	length = i;
  45. }
  46.  
  47. //图权重初始化
  48. void GraphWeightInit()
  49. {
  50. 	int i, j;
  51. 	for (i = 0; i < length; i++)
  52. 	{
  53. 		for (j = 0; j < length; j++)
  54. 		{
  55. 			if (i == j)							//指向自己
  56. 				G.weight[i][j] = 0;
  57. 			else
  58. 				G.weight[i][j] = MAX;	//无穷大
  59. 		}
  60. 	}
  61. }
  62.  
  63. //根据数据查找图顶点下标
  64. int FindIndex(char ch)
  65. {
  66. 	int i;
  67. 	for (i = 0; i < length; i++)
  68. 	{
  69. 		if (G.vertex[i] == ch)
  70. 			return i;
  71. 	}
  72. 	return -1;
  73. }
  74.  
  75. //创建图
  76. void CreateGraph()
  77. {
  78. 	int i, j, index, weight;
  79. 	char ch;
  80. 	for (i = 0; i < length; i++)
  81. 	{
  82. 		printf("请输入%c的邻接顶点及权重（空格分隔，换行结束）：\n", G.vertex[i]);
  83. 		scanf("%c", &ch);
  84. 		while (ch != '\n')
  85. 		{
  86. 			while (ch == ' ')				//为空格
  87. 			{
  88. 				scanf("%c", &ch);			//输入字符
  89. 				continue;
  90. 			}
  91. 			index = FindIndex(ch);
  92. 			scanf("%d", &weight);		//输入权重
  93. 			while (weight == 32)		//32为空格的ASCII码
  94. 			{
  95. 				scanf("%d", &weight);
  96. 				continue;
  97. 			}
  98. 			G.weight[i][index] = weight;	//存入权重
  99. 			scanf("%c", &ch);				//(下一轮)输入字符
  100. 		}
  101. 	}
  102. }
  103.  
  104. //弗洛伊德算法
  105. void Floyd()
  106. {
  107. 	int medium, begin, end;
  108. 	//初始化矩阵
  109. 	for (int i = 0; i < length; i++)
  110. 		for (int j = 0; j < length; j++)
  111. 		{
  112. 			D[i][j] = G.weight[i][j];
  113. 			P[i][j] = j;
  114. 		}
  115.  
  116. 	//开始正式修改（最短路径及前驱）
  117. 	for (medium = 0; medium < length; medium++)	//中间结点
  118. 		for (begin = 0; begin < length; begin++)			//前驱结点
  119. 			for (end = 0; end < length; end++)				//后继结点
  120. 			{
  121. 				//经过中间结点路径更小，则1、需要覆盖掉原来的路径；2、替换掉前驱（中间结点）
  122. 				if (D[begin][end] > (D[begin][medium] + D[medium][end]))
  123. 				{
  124. 					D[begin][end] = D[begin][medium] + D[medium][end];		//覆盖路径（只达标的话，只要这一句就够了）
  125. 					P[begin][end] = P[begin][medium];										//更新前驱（中间结点）
  126. 					//不能直接赋值medium：跨越结点之间的追溯，存放的是最近前驱，需要一个一个往后追溯
  127. 				}
  128. 			}
  129. }
  130.  
  131. //测试矩阵输出
  132. void PrintArray()
  133. {
  134. 	//遍历输出
  135. 	printf("遍历输出D矩阵（最短路径）：\n");
  136. 	for (int i = 0; i < length; i++)
  137. 	{
  138. 		printf("\n");
  139. 		for (int j = 0; j < length; j++)
  140. 		{
  141. 			printf("%3d", D[i][j]);
  142. 		}
  143. 	}
  144. 	printf("\n遍历输出P矩阵（前驱）：\n");
  145. 	for (int i = 0; i < length; i++)
  146. 	{
  147. 		printf("\n");
  148. 		for (int j = 0; j < length; j++)
  149. 		{
  150. 			printf("%3d", P[i][j]);
  151. 		}
  152. 	}
  153. }
  154.  
  155. //遍历弗洛伊德算法
  156. //确定begin -> end：从最近的前驱开始，一点一点往后追溯
  157. void Traverse_Floyd()
  158. {
  159. 	int medium = 0;
  160. 	for (int begin = 0; begin < length; begin++)
  161. 	{
  162. 		for (int end = 0; end < length; end++)
  163. 		{
  164. 			printf("\n%c", G.vertex[begin]);
  165. 			medium = P[begin][end];						//开始追溯（此为最近的前驱）
  166. 			while (medium != end)							//未追溯到尾
  167. 			{
  168. 				printf("->%c", G.vertex[medium]);		//打印中间结点
  169. 				medium = P[medium][end];				//向后追溯
  170. 			}
  171. 		}
  172. 	}
  173. }
  174.  
  175. //输出测试
  176. void Print()
  177. {
  178. 	for (int i = 0; i < length; i++)
  179. 	{
  180. 		printf("\n%c结点邻接结点：\t", G.vertex[i]);
  181. 		for (int j = 0; j < length; j++)
  182. 		{
  183. 			if (G.weight[i][j] != 0 && G.weight[i][j] != MAX)		//有邻接结点
  184. 			{
  185. 				printf("%c %d\t", G.vertex[j], G.weight[i][j]);
  186. 			}
  187. 		}
  188. 	}
  189. }
  190.  
  191. int main()
  192. {
  193. 	InputVertex();			//输入顶点
  194.  
  195. 	GraphWeightInit();		//图权重初始化
  196.  
  197. 	CreateGraph();			//创建图
  198.  
  199. 	Floyd();				//弗洛伊德算法（生成最短路径）
  200. 	Traverse_Floyd();		//遍历弗洛伊德算法
  201. 	//PrintArray();			//测试弗洛伊德矩阵输出
  202. 	//Print();				//测试输出
  203.  
  204. 	return 0;
  205. }



参考资料

《大话数据结构》 

https://www.bilibili.com/video/BV1uX4y137Hf?from=search&seid=9442880507495572891

https://blog.csdn.net/jeffleo/article/details/53349825?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-53349825.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

https://blog.csdn.net/yuewenyao/article/details/81021319?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-81021319.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

https://zhuanlan.zhihu.com/p/33162490 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/822107
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号