最短路径Dijkstra算法实验报告.doc

最短路径Dijkstra算法实验报告.doc:..班级:030913班姓名:张进 学号:03091256实验六:•需求分析:首先让用户输入一个带权的有向图,输入时可通过一对一对输入存在弧的两个弧头与弧尾顶点以及弧上的权值从而输入整个有向图。用户输入一对对弧后,我们可以采用数组的形式来进行存储每个顶点之间的权值,最后由用户输入该有向图的源点(即每个最短路径的起点),要求源点必须为刚才输入的各顶点中的某一个,如果用户输入错误,程序耍给出错误信息提示并退出程序。然后,我们可以设计一个Graph这样的类,将对关系的各种操作放入其中,然后我们在主函数中调运这个类就可以实现最短路问题的求解了。:①•构造一个新的类Graph:classGraph{private:intarcs[MAX][MAX],Path[MAX][MAX],D[MAX];um,vexnum,weight,vO;Typea,b,vexs[MAX];■■voidCreat_Grciph();voidShowShortestPath():voidShortestPathDTJ();};②结构化调用类中方法的主函数:intmain(){Graph<char>G;,Graph();!J():();return0;}:#include<iostream>^defineMAX100^NFTNTTYTNT_MAXenumBOOL(FALSE,TRUE);usingnamespacestd;template<typenameType>classGraphprivate:intarcs[MAX][MAX],Path[MAX][MAX],D[MAX];um,vcxnum,weight,vO;Typea,b,vexs[MAX];public:voidCreatGraph():voidShowShortestPath();voidShorteslPath_DIJ();template<typenameType>voidGraph<Type>::CroatGraph()inti,j,x,y;cout<<〃请输入你要处理的有向图屮包含弧的个数:〃;cin>>um;vexnum=0;for(i=l;iUMAX;i++)for(j=l;j〈=MAX;j++)arcs[i][j]=TNTMAX;for(i=l;i<=um;i++){cout«"请依次输入笫条弧的弧头与弧尾的顶点以及该弧上所附带的权值:,,«endl;cin»a»b»weight;x=0; y=0;for(j=l;j<=vexnum;j++)if(vexs[j]=a)x=j;continue;)elseif(vexs[j]==b)y=j;continue;)if(x==0)vexs[++vexnum]二臼; x^vexnum;if(y==0)vexs[++vexnum]=b;y=vexnum;arcs[x][y]二weight;)cout<<〃请输入该冇向图的源点(即各最短路径的起始顶点):〃;cin>>a;for(i=l;i<=vexnum;i++){if(vex