《C两点间距离最短最精板》由会员分享，可在线阅读，更多相关《C两点间距离最短最精板（9页珍藏版）》请在金锄头文库上搜索。
1、一、 实验内容： 考虑右边的无向图，设计算法输出从顶点a到顶点i的一条带权路径长度最短的简单路径。分析时间和空间复杂度。实验要求：采用递归或非递归的深度优先或广度优先遍历算法扩展实现。二、 算法思想：构造一个带权无向图，采用深度优先遍历的方法，每走到一个点就用visited做访问过的标记，这样循环递归找到顶点a到i的所有路径，再比较所有路径的长度，找到最短路径。三、 实验过程：#include#include#includeusing namespace std;#define MAX_VEX_NUM 20/最大顶点数vectorallPath; /向量，用来存放所有的顶点a到顶点i的路径ve
2、ctorall;struct MGraphchar vexsMAX_VEX_NUM;/顶点向量/AdjMatrixint arcsMAX_VEX_NUMMAX_VEX_NUM;/邻接矩阵int vexnum,arcnum;MGraph G;/申明一个无向图的邻接矩阵类型int Locatevex(MGraph G,char v)/图的基本操作，寻找V的位置 int i=0;while(iG.vexnum&v!=G.vexsi) i+;if(iG.vexnum) return i;/查找成功则返回顶点的下标else return -1;int CreateUDG(MGraph&G)/数组邻接矩阵
3、表示法构造无向图 char v1,v2; int weight;/权值 cout请输入图的顶点数和弧数G.vexnumG.arcnum; cout请输入顶点值endl; for(int i=0;iG.vexsi; for(int q=0;qG.vexnum;q+)/初始化邻接矩阵for(int p=0;pG.vexnum;p+) G.arcsqwwp=0;for(int k=0;kG.arcnum;k+)/构造邻接矩阵 cout输入该弧依附的顶点和权值:v1v2weight; int a=Locatevex(G,v1); int b=Locatevex(G,v2); G.arcsab=weig
4、ht; G.arcsba=G.arcsab; for(int n=0;nG.vexnum;n+)/输出顶点 coutG.vexsn ; coutendl; coutendl;cout该图的邻接矩阵表示为: n;for(int x=0;x=G.vexnum;x+)/输出邻接矩阵 for(int y=0;yG.vexnum;y+) coutG.arcsxy ; coutendl;coutendl;coutendl;return 1;/CreateUDG void Minway(MGraph G,bool*visited,char vexs,int Long,char vb,string path)
5、 / if(vexs=vb) /递归结束条件 path=path+ +vexs; allPath.push_back(path); /将路径放入向量中 all.push_back(Long); /将路径长放入对应向量中 cout路径:path长度:Longendl;else path=path+ +vexs; int i=Locatevex(G,vexs); visitedi=true; for(int j=0;jG.vexnum;j+) if(!visitedj)&(G.arcsij!=0) Minway(G,visited,G.vexsj,Long+G.arcsij,vb,path); /
6、递归调用自身 visitedi=false; /退出递归前清除访问记录 void CountMinway(MGraph G) /该函数调用递归部分实现递归 char va, vb; string path; /存放路径 coutvavb; coutendl; int i=Locatevex(G,va); bool visited100; for(int j=0;jG.vexnum;j+) visitedj=false; /初始化访问记录，全部未访问过 visitedi=true; /起点顶点设为访问过 int Long=0; path+=va; for(j=0;jG.vexnum;j+) if
7、(G.arcsij!=0) Long=G.arcsij; Minway (G,visited,G.vexsj,Long,vb,path); /调用递归部分 coutendl; void Minway()/输出最短路径int min=10000;for(int i=0;iallPath.size();i+) if(allimin) min=alli;for(int j=0;jallPath.size();j+) if(allj=min) cout 最短路径:allPathj长度:alljendl;coutendl;void main() CreateUDG(G);/建图 CountMinway(G);/找出所有路径 Minway(); /输出最短路径四、 实验结果：五、 小结：
