最短路径问题-实验报告

HUNANUNIVERSITY课程实习报告题目：最短路径学生姓名学生学号专业班级指导老师吴帆完成日期201：年6月6日HUNANUNIVERSITY课程实习报告、需求分析：1、本程序需要用矩阵来存储图的各种信息。2、测试数据输入（文件）5-110320-1-1-1-15-1-12-1-115-1-1-1-111-1-1-1-1-1（用户）起点0终点4输出18二、概要设计:抽象数据类型:为实现上述功能需建立一个二维数组和图类。算法的基本思想：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（"途中各点之间的距离）。2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离11和直接到其他点的距离12。如果11<12，则用11的距离替换12。重复上述操作n-1（n为结点数）次。得到的即为第一个结点到其他结点的最短距离。程序的流程程序由三个模块组成：输入模块：读入图的信息（用矩阵进行存储）。处理模块：Dijkstra算法。输出模块：将收入结点到其他点的最短距离输出。二、详细设计图类：c1assGraph成员函数：Graph（intv）（ver=v;}voidbuild(ifstreamfilel);voidDijkstra(intstart,intend);voidprintf(intstart);数据成员：intver;四、调试分析总是出现wrong,即文件打开错误。原因是在代码最后没有写“file1.close();”写入后程序运行正确，结果正确，但最后还是会弹出内存错误的窗口。五、测试结果输人两个顶焉w40->4:18Pressanykeytocontinue输人两个顶焉w40->4:18Pressanykeytocontinue注：顶点个数和矩阵从文件中读入。六、实验心得这次的试验主要是对Dijkstra算法的应用，还有从文件中读取数据。主要用到了文件的输入输出流，跟cin，cout很相似，但在最后一定要关闭文件，否则就会出错。实践出真知，通过编写代码，我对最短路径问题的理解就比较透彻了。不过没有用到优先队列与堆，对优先队列的应用还不太熟练。七、附录：#include<iostream>#include<fstream>usingnamespacestd;#defineN30inta[N][N];classGraph(private:intver;public:Graph(intv)(ver=v;}voidbuild(ifstreamfile1);voidDijkstra(intstart,intend);voidprintf(intstart);};voidGraph::build(ifstreamfile1)(//构建图inttemp,max=1000;for(inti=0;i<ver;i++)for(intj=0;j<ver;j++){file1>>temp;if(temp==-1)//-1表示两点之间无直接联系，将距离赋为1000a[i][j]=1000;elsea[i][j]=temp;}}voidGraph::Dijkstra(intstart,intend)(//最小路径的算法intdist[N],s[N];inti,j,min,pos;for(i=0;i<ver;i++)(if(i==start)s[i]=1;//标记边是否被访问elses[i]=0;}for(i=0;i<ver;i++)dist[i]=a[start][i];//该点到其他边的距离for(i=0;i<ver-1;i++)(//共有n个顶点，故要重复n-1min=1000;pos=0;for(j=0;j<ver;j++)(if(s[j]==0&&dist[j]<min)(min=dist[j];〃找出最小边，则该边是最短路径所必须的pos=j;}}s[pos]=1;for(j=0;j<ver;j++)(if(dist[j]>dist[pos]+a[pos][j])〃如过通过pos这条边的距离小于原先的距离dist[j]=dist[pos]+a[pos][j];〃改变距离}}cout<<start<<"->"<<end<<":"<<dist[i]<<endl;}intmain()(intv,start,end;ifstreamfile1(〃d:\\zuiduanlujing.txt〃)；if(file1==NULL)cout<<"Wrong"<<endl;file1>>v;GraphG