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

c/c++常用算法(15) -- 经典数据结构(城市之间的最短距离问题)_计算机城市最小距离

作者：Gausst松鼠会 | 2024-03-15 18:20:48

赞

踩

计算机城市最小距离

一、最短总距离算法:


1.描述


        我们先来分析一下这个问题。某个地区n个城市构成一个交通图,我们可以使用图结构来描述这个问题，其对应关系如下:

  • 每个城市代表一个图中的一个顶点。
  • 两个顶点之间的边就是两个城市之间的路径,边的权值代表了城市间的距离。

        这样，求解各个城市之间的最短总距离问题就归结为该图的最小生成树问题。


2.最小生成树


        一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。如图：





3.基本思想


        假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：
           在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。
           此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。


4.实现代码(最短总距离算法)

  1. #include <iostream>
  2. #include <time.h>
  3. #include <string.h>
  4.  
  5. #define MaxNum 20           //图的最大顶点数
  6. #define MaxValue 65535      //最大值
  7.  
  8. #define USED 0;             //已选用顶点
  9. #define NoL -1              //非邻接顶点
  10.  
  11. typedef struct
  12. {
  13. 	char Vertex[MaxNum];            //保存顶点信息(序号或字母)
  14. 	int GType;                      //图的类型(0:无向图,1)
  15. 	int VertexNum;                  //顶点的数量
  16. 	int EdgeNum;                    //边的数量
  17. 	int EdgeWeight[MaxNum][MaxNum]; //保存边的权
  18. 	int isTrav[MaxNum];             //定义邻接矩阵图结构
  19. }GraphMatrix;
  20.  
  21. void CreateGraph(GraphMatrix *GM)
  22. {
  23. 	int i,j,k;
  24. 	int weight;
  25. 	char EstartV,EendV;
  26.     
  27. 	std::cout<<"输入图中各顶点信息\n";
  28. 	for (i = 0; i<GM->VertexNum; i++)
  29. 	{
  30. 		getchar();
  31. 		printf("第%d个顶点:",i+1);
  32. 		scanf("%c",&(GM->Vertex[i]));
  33. 	}
  34. 	std::cout<<"输入构成各边的顶点及权值:\n";
  35. 	for (k = 0; k <GM->EdgeNum; k++)
  36. 	{
  37. 		getchar();
  38. 		printf("第%d条边:",k+1);
  39. 		scanf("%c %c %d",&EstartV,&EendV,&weight);
  40. 		for ( i= 0; EstartV != GM->Vertex[i]; i++);
  41. 		for ( j= 0; EendV != GM->Vertex[j]; j++);
  42. 		GM->EdgeWeight[i][j] = weight;
  43. 		if (GM->GType == 0) //若是无向图
  44. 		{
  45. 			GM->EdgeWeight[j][i] = weight;
  46. 		}
  47. 	}
  48. }
  49.  
  50. void ClearGraph(GraphMatrix *GM)
  51. {
  52. 	int i,j;
  53. 	for (i=0; i<GM->VertexNum; i++)
  54. 	{
  55. 		for (j=0; j<GM->VertexNum; j++)
  56. 		{
  57. 			GM->EdgeWeight[i][j] = MaxValue;
  58. 		}
  59. 	}
  60. }
  61.  
  62. void OutGraph(GraphMatrix *GM)
  63. {
  64. 	int i,j;
  65. 	for (j=0; j<GM->VertexNum; j++)
  66. 	{
  67. 		printf("\t%c",GM->Vertex[j]);
  68. 	}
  69. 	std::cout<<"\n";
  70.     
  71. 	for (i=0; i<GM->VertexNum; i++)
  72. 	{
  73. 		printf("%c",GM->Vertex[i]);
  74. 		for (j=0; j<GM->VertexNum; j++)
  75. 		{
  76. 			if (GM->EdgeWeight[i][j] == MaxValue)
  77. 			{
  78. 				printf("\tZ");  //以Z表示无穷大
  79. 			}
  80. 			else
  81. 			{
  82. 				printf("\t%d",GM->EdgeWeight[i][j]);  //输出边的权值
  83. 			}
  84. 		}
  85. 		std::cout<<"\n";
  86. 	}
  87. }
  88.  
  89. void PrimGraph(GraphMatrix GM)          //最小生成树算法
  90. {
  91. 	int i,j,k,min,sum;
  92. 	int weight[MaxNum];                 //权值
  93. 	char vtempx[MaxNum];                //临时顶点信息
  94.     
  95. 	sum = 0;
  96. 	for(i = 1; i<GM.VertexNum;i++)      //保存邻接矩阵中的一行数据
  97. 	{
  98. 		weight[i] = GM.EdgeWeight[0][i];
  99. 		if (weight[i] == MaxValue)
  100. 		{
  101. 			vtempx[i] = NoL;
  102. 		}
  103. 		else
  104. 		{
  105. 			vtempx[i] = GM.Vertex[0];               //邻接顶点
  106. 		}
  107. 	}
  108. 	vtempx[0] = USED;                               //选用
  109. 	weight[0] = MaxValue;
  110. 	for (i = 1; i<GM.VertexNum; i++)
  111. 	{
  112. 		min = weight[0];                            //最小权值
  113. 		k = i;
  114. 		for (j = 1; j<GM.VertexNum; j++)
  115. 		{
  116. 			if (weight[j] < min && vtempx[j]>0)     //到具有更小权值的未使用边
  117. 			{
  118. 				min = weight[j];                    //保存权植
  119. 				k = j;                              //保存邻接点序号
  120. 			}
  121. 		}
  122. 		sum +=min;                                  //权值累加
  123. 		printf("(%c,%c),",vtempx[k],GM.Vertex[k]);  //输出生成树一条边
  124. 		vtempx[k] = USED;
  125. 		weight[k] = MaxValue;
  126. 		for (j = 0; j<GM.VertexNum; j++)            //重新选择最小边
  127. 		{
  128. 			if (GM.EdgeWeight[k][j] < weight[j] && vtempx[j]!= 0)
  129. 			{
  130. 				weight[j] = GM.EdgeWeight[k][j];    //权植
  131. 				vtempx[j] = GM.Vertex[k];
  132. 			}
  133. 		}
  134. 	}
  135. 	printf("\n最小生成树的总权值为:%d\n",sum);
  136. }
  137.  
  138.  
  139. int main(int argc, const char * argv[])
  140. {
  141. 	// std::cout << "Hello, World!\n";
  142. 	GraphMatrix GM;
  143. 	char again;
  144.     
  145. 	printf("寻找最小生成树!\n");
  146.     
  147. 	printf("请先输入生成图的类型:");
  148. 	scanf("%d",&GM.GType);
  149. 	printf("输入图的顶点数量:");
  150. 	scanf("%d",&GM.VertexNum);
  151.     
  152. 	printf("输入图的边数量:");
  153. 	scanf("%d",&GM.EdgeNum);
  154.     
  155. 	ClearGraph(&GM);
  156. 	CreateGraph(&GM);
  157. 	printf("该图的邻接矩阵数据如下:\n");
  158. 	OutGraph(&GM);
  159.     
  160. 	printf("最小生成树的边为:");
  161. 	PrimGraph(GM);
  162.     
  163. 	printf("\n继续玩(y/n)");
  164. 	fflush(stdin);
  165. 	scanf("%c",&again);
  166.     
  167.     
  168. 	printf("\n");
  169.     
  170.     
  171. 	return 0;
  172. }

演示结果:


                


演示效果图:


                


二、最短路径


1.描述


        求解城市之间的最短距离是一个非常实际的问题。其大意如下:

        某个地区有n个城市,如何选择路线使某个城市到某个指定城市的距离最短?


        注：这里需要求解的最短路径指两个城市之间的最短距离，面不是所有城市之间最短总距离。


2.基本思想


算法步骤如下：


        1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
                若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
                若不存在<V0,Vi>，d(V0,Vi)为∞
        2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
        3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止


3.实现代码

                

  1. #include <iostream>
  2. #include <time.h>
  3. #include <string.h>
  4.  
  5. #define MaxNum 20           //图的最大顶点数
  6. #define MaxValue 65535      //最大值
  7. int  path[MaxNum];          //两点经过的顶点集合的数组
  8. int tmpvertex[MaxNum];      //最短路径的起始点集合
  9.  
  10. #define USED 0;             //已选用顶点
  11. #define NoL -1              //非邻接顶点
  12.  
  13. typedef struct
  14. {
  15. 	char Vertex[MaxNum];            //保存顶点信息(序号或字母)
  16. 	int GType;                      //图的类型(0:无向图,1)
  17. 	int VertexNum;                  //顶点的数量
  18. 	int EdgeNum;                    //边的数量
  19. 	int EdgeWeight[MaxNum][MaxNum]; //保存边的权
  20. 	int isTrav[MaxNum];             //定义邻接矩阵图结构
  21. }GraphMatrix;
  22.  
  23. void CreateGraph(GraphMatrix *GM)
  24. {
  25. 	int i,j,k;
  26. 	int weight;
  27. 	char EstartV,EendV;
  28.     
  29. 	std::cout<<"输入图中各顶点信息\n";
  30. 	for (i = 0; i<GM->VertexNum; i++)
  31. 	{
  32. 		getchar();
  33. 		printf("第%d个顶点:",i+1);
  34. 		scanf("%c",&(GM->Vertex[i]));
  35. 	}
  36. 	std::cout<<"输入构成各边的顶点及权值:\n";
  37. 	for (k = 0; k <GM->EdgeNum; k++)
  38. 	{
  39. 		getchar();
  40. 		printf("第%d条边:",k+1);
  41. 		scanf("%c %c %d",&EstartV,&EendV,&weight);
  42. 		for ( i= 0; EstartV != GM->Vertex[i]; i++);
  43. 		for ( j= 0; EendV != GM->Vertex[j]; j++);
  44. 		GM->EdgeWeight[i][j] = weight;
  45. 		if (GM->GType == 0) //若是无向图
  46. 		{
  47. 			GM->EdgeWeight[j][i] = weight;
  48. 		}
  49. 	}
  50. }
  51.  
  52. void ClearGraph(GraphMatrix *GM)
  53. {
  54. 	int i,j;
  55. 	for (i=0; i<GM->VertexNum; i++)
  56. 	{
  57. 		for (j=0; j<GM->VertexNum; j++)
  58. 		{
  59. 			GM->EdgeWeight[i][j] = MaxValue;
  60. 		}
  61. 	}
  62. }
  63.  
  64. void OutGraph(GraphMatrix *GM)
  65. {
  66. 	int i,j;
  67. 	for (j=0; j<GM->VertexNum; j++)
  68. 	{
  69. 		printf("\t%c",GM->Vertex[j]);
  70. 	}
  71. 	std::cout<<"\n";
  72.     
  73. 	for (i=0; i<GM->VertexNum; i++)
  74. 	{
  75. 		printf("%c",GM->Vertex[i]);
  76. 		for (j=0; j<GM->VertexNum; j++)
  77. 		{
  78. 			if (GM->EdgeWeight[i][j] == MaxValue)
  79. 			{
  80. 				printf("\tZ");  //以Z表示无穷大
  81. 			}
  82. 			else
  83. 			{
  84. 				printf("\t%d",GM->EdgeWeight[i][j]);  //输出边的权值
  85. 			}
  86. 		}
  87. 		std::cout<<"\n";
  88. 	}
  89. }
  90.  
  91. void DisMin(GraphMatrix GM,int vend)    //最短路径算法
  92. {
  93.     int weight[MaxNum];                 //某终止点到各顶点的最短路径长度
  94.     int i,j,k,min;
  95.     vend--;
  96.     
  97.     for (i =0; i<GM.VertexNum; i++)             //初始weight数组
  98.     {
  99.         weight[i] = GM.EdgeWeight[vend][i];     //保存最小权值
  100.     }
  101.     
  102.     for (i=0; i<GM.VertexNum; i++)              //初始path数组
  103.     {
  104.         if (weight[i]<MaxValue && weight[i]>0)  //有效权值
  105.         {
  106.             path[i] = vend;                     //保存边
  107.         }
  108.     }
  109.     
  110.     for (i=0; i<GM.VertexNum; i++)              //初始tmpvertex数组
  111.     {
  112.         tmpvertex[i] = 0;                       //初始化顶点集合为空
  113.     }
  114.     
  115.     tmpvertex[vend] = 1;                        //选入顶点vend
  116.     weight[vend] = 0;
  117.     for (i = 0; i<GM.VertexNum; i++)
  118.     {
  119.         min = MaxValue;
  120.         k = vend;
  121.         for (j=0; j < GM.VertexNum; j++)
  122.         {
  123.             if (tmpvertex[j] == 0 && weight[j] <min)    //查找未用顶点的最小权值
  124.             {
  125.                 min = weight[j];
  126.                 k = j;
  127.             }
  128.         }
  129.         
  130.         tmpvertex[k] = 1;                               //将顶点k选入
  131.         for (j = 0; j<GM.VertexNum; j++)
  132.         {
  133.             if (tmpvertex[j] == 0 && weight[k] + GM.EdgeWeight[k][j] < weight[j])
  134.             {
  135.                 weight[j] = weight[k] + GM.EdgeWeight[k][j];
  136.                 path[j] = k;
  137.             }
  138.         }
  139.     }
  140. }
  141.  
  142.  
  143.  
  144. int main(int argc, const char * argv[])
  145. {
  146. 	// std::cout << "Hello, World!\n";
  147. 	GraphMatrix GM;
  148. 	char again;
  149.     int vend;
  150.     int i,k;
  151.     
  152. 	printf("求解最短路径问题!\n");
  153.     
  154. 	printf("请先输入生成图的类型:");
  155. 	scanf("%d",&GM.GType);
  156. 	printf("输入图的顶点数量:");
  157. 	scanf("%d",&GM.VertexNum);
  158.     
  159. 	printf("输入图的边数量:");
  160. 	scanf("%d",&GM.EdgeNum);
  161.     
  162. 	ClearGraph(&GM);
  163. 	CreateGraph(&GM);
  164. 	
  165.     printf("\n请输入结束点:");
  166.     scanf("%d",&vend);
  167.     
  168.     DisMin(GM, vend);
  169.     
  170.     vend--;
  171.     printf("\n各顶点到达顶点%c的最短路径分别为(起始点-结束点):\n",GM.Vertex[vend]);
  172.     for (i = 0; i <GM.VertexNum; i++)
  173.     {
  174.         if (tmpvertex[i] == 1)
  175.         {
  176.             k = i;
  177.             while (k != vend)
  178.             {
  179.                 printf("顶点%c-",GM.Vertex[k]);
  180.                 k = path[k];
  181.             }
  182.             printf("顶点%c\n",GM.Vertex[k]);
  183.         }
  184.         else
  185.         {
  186.             printf("%c - %c:无路径\n",GM.Vertex[i],GM.Vertex[vend]);
  187.         }
  188.     }
  189.     
  190. 	printf("\n");
  191.     
  192.     
  193. 	return 0;
  194. }
演示结果:

                


演示效果图:


                


参考书籍:《C/C++常用算法手册》

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

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

  

闽ICP备14008679号