最短路径Dijkstra算法实验报告

《最短路径Dijkstra算法实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、姓名：张进学号：03091256班级：030913班实验六：编程实现Dijkstra算法求最短路问题.1.需求分析：首先让用户输入一个带权的有向图，输入时可通过一对一对输入存在弧的两个弧头与弧尾顶点以及弧上的权值从而输入整个有向图。用户输入一对对弧后，我们可以采用数组的形式来进行存储每个顶点之间的权值，最后由用户输入该有向图的源点（即每个最短路径的起点），要求源点必须为刚才输入的各顶点中的某一个，如果用户输入错误，程序要给出错误信息提示并退出程序。然后，我们可以设计一个Graph这样的类，将对关系的各种操作放入其中，然后我们在主函数中调运这个类就可以实现最短路问题的求解了。2

2、.概要设计：①.构造一个新的类Graph:classGraph{private:intarcs[MAX][MAX],Path[MAX][MAX],D[MAX];intarcnum,vexnum,weight,v0;Typea,b,vexs[MAX];public:voidCreat_Graph();voidShow_ShortestPath();voidShortestPath_DIJ();};②.结构化调用类中方法的主函数：intmain(){GraphG;G.Creat_Graph();G.ShortestPath_DIJ();G.Show_ShortestP

3、ath();return0;}3.代码实现：#include#defineMAX100#defineINFINITYINT_MAXenumBOOL{FALSE,TRUE};usingnamespacestd;templateclassGraph{private:intarcs[MAX][MAX],Path[MAX][MAX],D[MAX];intarcnum,vexnum,weight,v0;Typea,b,vexs[MAX];public:voidCreat_Graph();voidShow_ShortestPath();vo

4、idShortestPath_DIJ();};templatevoidGraph::Creat_Graph(){inti,j,x,y;cout<<"请输入你要处理的有向图中包含弧的个数：";cin>>arcnum;vexnum=0;for(i=1;i<=MAX;i++)for(j=1;j<=MAX;j++)arcs[i][j]=INT_MAX;for(i=1;i<=arcnum;i++){cout<<"请依次输入第"<>a>>b>>weight;x=0;y=

5、0;for(j=1;j<=vexnum;j++){if(vexs[j]==a){x=j;continue;}elseif(vexs[j]==b){y=j;continue;}}if(x==0){vexs[++vexnum]=a;x=vexnum;}if(y==0){vexs[++vexnum]=b;y=vexnum;}arcs[x][y]=weight;}cout<<"请输入该有向图的源点(即各最短路径的起始顶点)：";cin>>a;for(i=1;i<=vexnum;i++){if(vexs[i]==a){v0=i;break;}}}template

6、e>voidGraph::Show_ShortestPath(){inti,j,k;for(i=1;i<=vexnum;i++){if(i==v0)continue;if(D[i]!=INT_MAX){cout<<"从源点"<";for(j=1;j<=vexnum;j++)if(Path[i][j]==k)cout<

7、endl;}else{cout<<"无法从源点"<voidGraph::ShortestPath_DIJ(){intv,w,final[MAX],min,i,j;for(v=1;v<=vexnum;v++){final[v]=FALSE;D[v]=arcs[v0][v];Path[v][0]=0;for(w=0;w<=vexnum;w++)Pat