数据结构实验4 最短路径算法

《数据结构实验4 最短路径算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验4最短路径算法一、实验目的1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。2．掌握图的存储结构以及单源点最短路径算法。二、实验内容1.理解Dijkstra算法的原理，用Dijkstra算法编程找出从s到t的最短路径。2.编程实现Dijkstra算法，三、需求分析：首先让用户输入一个带权的有向图，输入时可通过一对一对输入存在弧的两个弧头与弧尾顶点以及弧上的权值从而输入整个有向图。用户输入一对对弧后，我们可以采用数组的形式来进行存储每个顶点之间的权值，最后由用户输入该有向图的源点（即每个最短路径的起点），要求源点必须为刚才输入的各

2、顶点中的某一个，如果用户输入错误，程序要给出错误信息提示并退出程序。然后，我们可以设计一个Graph这样的类，将对关系的各种操作放入其中，然后我们在主函数中调运这个类就可以实现最短路问题的求解了。四、概要设计：①.构造一个新的类Graph:classGraph{private:intarcs[MAX][MAX],Path[MAX][MAX],D[MAX];intarcnum,vexnum,weight,v0;Typea,b,vexs[MAX];public:voidCreat_Graph();voidShow_ShortestPath();void

3、ShortestPath_DIJ();};②.结构化调用类中方法的主函数：intmain(){GraphG;G.Creat_Graph();G.ShortestPath_DIJ();G.Show_ShortestPath();return0;}五、函数代码/****************************************About:有向图的Dijkstra算法实现*Author:TankyWoo*Blog:www.WuTianQi.com***************************************/#i

4、ncludeusingnamespacestd;constintmaxnum=100;constintmaxint=999999;//各数组都从下标1开始intdist[maxnum];//表示当前点到源点的最短路径长度intprev[maxnum];//记录当前点的前一个结点intc[maxnum][maxnum];//记录图的两点间路径长度intn,line;//图的结点数和路径数//n--nnodes//v--thesourcenode//dist[]--thedistancefromtheithnodetothesour

5、cenode//prev[]--thepreviousnodeoftheithnode//c[][]--everytwonodes'distancevoidDijkstra(intn,intv,int*dist,int*prev,intc[maxnum][maxnum]){bools[maxnum];//判断是否已存入该点到S集合中for(inti=1;i<=n;++i){dist[i]=c[v][i];s[i]=0;//初始都未用过该点if(dist[i]==maxint)prev[i]=0;elseprev[i]=v;}dist[v]=0;s[

6、v]=1;//依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中//一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度//注意是从第二个节点开始，第一个为源点for(inti=2;i<=n;++i){inttmp=maxint;intu=v;//找出当前未使用的点j的dist[j]最小值for(intj=1;j<=n;++j)if((!s[j])&&dist[j]

7、tfor(intj=1;j<=n;++j)if((!s[j])&&c[u][j]

8、[tmp];}que[tot]=v;for(inti=tot;i>=1;--i)if(i!=1)cout<