《《数据结构及其应用》实验报告模板.docxVIP

数据结构及其应用（上机）实 验 报 告专 业： 通信工程 班 级： 14通信一班 姓 名： 何月圆 学 号：实验成绩： 实验四 最短路径算法实现实验目的1、编程实现采用邻接矩阵表示法创建有向网2、编程实现最短路径Floyd算法3、进一步理解Floyd算法的原理实验环境1、Windows操作系统2、VC++ 6.0编译软件三、实验原理弗洛伊德（Floyd）算法原理：弗洛伊德算法使用带权的邻接矩阵arcs来表示有向网G，求顶点vi到vj短路径。算法实现需要引入两个辅助的数据结构：二维数组Path[i][j]：最短路径上顶点vj的前一顶点的序号。二维数组D[i][j]：记录顶点vi和vj之间的最短路径长度。四、实验过程（一）程序分析1、图的邻接矩阵2、邻接矩阵表示法创建有向网G3、loyd算法求有向网G中各对顶点i和j之间的最短路径2、算法描述#includeiostreamusing namespace std;#define MaxInt 32767#define MVNum 100typedef char VerTexType;typedef int ArcType;int Path[MVNum][MVNum];int D[MVNum][MVNum];typedef struct{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum,arcnum;}AMGraph;int LocateVex(AMGraph G,VerTexType v){for (int i=0;iG.vexnum;++i) if(G.vexs[i]==v) return i;return -1;}void CreateUDN(AMGraph G){int i,j,k;cout请输入总顶点数，总边数，以空格隔开：;cinG.vexnumG.arcnum;coutendl;cout输入点的名称，如aendl;for(i=0;iG.vexnum;++i){ cout请输入第(i+1)个点的名称：; cinG.vexs[i];}for(i=0;iG.vexnum;++i){ for(j=0;jG.vexnum;++j){ if(j!=i) G.arcs[i][j]=MaxInt; else G.arcs[i][j]=0;}}cout\n输入边依附的顶点及权值，如a b 3\nendl;for(k=0;kG.arcnum;++k){ VerTexType v1,v2; ArcType w; cout请输入第(k+1)条边依附的顶点及权值：; cinv1v2w; i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j]=w;}for(i=0;iG.vexnum;++i){for(j=0;jG.vexnum;++j){if(j!=G.vexnum-1){if(G.arcs[i][j]!=MaxInt)coutG.arcs[i][j]\t;elsecout∞\t;}else{if(G.arcs[i][j]!=MaxInt)coutG.arcs[i][j]endl;elsecout∞endl;}}}}void ShortestPath_Floyed(AMGraph G){int i,j,k;for(i=0;iG.vexnum;++i)for(j=0;jG.vexnum;++j){D[i][j]=G.arcs[i][j];if(D[i][j]MaxInti!=j) Path[i][j]=i;else Path[i][j]=-1;}for(k=0;kG.vexnum;++k)for(i=0;iG.vexnum;++i)for(j=0;jG.vexnum;++j)if(D[i][k]+D[k][j]D[i][j]){D[i][j]=D[i][k]+D[k][j];Path[i][j]=Path[k][j];}}void DisplayPath(AMGraph G,int begin,int temp){if(Path[begin][temp]!=-1){DisplayPath(G,begin,Path[begin][temp]);coutG.vexs[Path[begin][temp]]--;}}void main(){cout************算法6.11 弗洛伊德算法************\n;AMGraph G;char start,destination;int num_start,num_destination;CreateUDN(G);coutendl;cout有向网G创建完成！endl;ShortestPath_F