有向图的最短路径.docx

《有向图的最短路径.docx》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验卡课程名称数据结构与算法班级顺序号11实验名称实验11有向图的最短路径实验目的（1）掌握有向图的邻接矩阵表示；（2）掌握有向图的邻接矩阵表示及最短路径的计算。实验内容【题目描述】用邻接矩阵表示有向图，并实现Dijkstra算法。假设有如下有向图：13024105030101002060按邻接矩阵的方式存储此有向图，并实现Dijkstra算法输出最短路径。【输入】输入有向图G的顶点数n，边数m;输入顶点的值；端点信息、权值。【输出】输出图的顶点和边的信息；某个源点到其余各顶点的最短路径，最短路径长度。#i

2、nclude#includeusingnamespacestd;#defineMAX_VERTEX_NUM10//最大顶点个数#defineTRUE1#defineFALSE0#defineINFINITY32767/*用整型最大值代替∞*/typedefcharVERTYPE;typedefstruct{VERTYPEvexs[MAX_VERTEX_NUM];//顶点向量intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵int

3、vexnum,arcnum;//图的当前顶点数和弧数}mgraph,*MGraph;typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintShortPathTable[MAX_VERTEX_NUM];voidinit_mgraph(MGraph&g)//初始化图{g=(MGraph)malloc(sizeof(mgraph));g->vexnum=0;g->arcnum=0;for(inti=0;i

4、)g->vexs[i]=0;for(i=0;iarcs[i][j]=INFINITY;}voidadd_vexs(MGraph&g)//增加顶点{cout<<"请输入顶点的个数:"<>g->vexnum;cout<<"请输入顶点的值"<vexnum;i++){cin>>g->vexs[i];}}voidadd_arcs(MGraph&g

5、)//增加边{cout<<"请输入边的个数:"<>g->arcnum;VERTYPEch1,ch2;introw,col,weight;cout<<"请输入顶点，顶点，边长："<arcnum;i++){cin>>ch1>>ch2>>weight;for(intj=0;jvexnum;j++){if(g->vexs[j]==ch1){row=j;}if(g->vexs[j]==ch2){col=j;}}g->arcs[row][col]=

6、weight;//有向带权图只需把1改为weight}}voidcreat_mgraph(MGraph&g)//创建图{add_vexs(g);//增加顶点add_arcs(g);//增加边}voidprint_mgraph(MGraph&g)//打印图{for(inti=0;ivexnum;i++)cout<<""<vexs[i]<<"";cout<vexnum;i++){cout<vexs[i]<<"";for(intj=0;jvex

7、num;j++){cout<arcs[i][j]<<"";}cout<

8、j,min;intfinal[MAX_VERTEX_NUM];for(v=0;vvexnum;++v){final[v]=FALSE;(*D)[v]=g->arcs[v0][v];for(w=0;wvexnum;++w)(*P)[v][w]=FALSE;//设空路径if((*D)[v]