《数据结构》实验报告学号2015011512 姓名胡明禹专业数学与应用数学时间2018.6.5一、实验题目: 实验八最短路径二、实验目的1. 掌握杰斯特拉算法2. 利用迪杰斯特拉算法计算途中一点到其他各顶点的最短路径三、算法设计分析实验由4个函数共同组成。

其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能void main()（2）创建有向图的邻接矩阵函数Status CreateDG(MGraph &G){int i,j,k,w;char v1,v2;printf("请输入顶点数和边数：");scanf("%d%d",&G.vexnum,&G.arcnum);printf("\n请按次序输入%d个顶点字母标号(如ABCD等)：",G.vexnum);getchar(); //弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for (i=0;i<G.vexnum;i++)scanf("%c",&G.vexs[i]);getchar(); //弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for (i=0;i<G.vexnum;++i) //初始化邻接矩阵for (j=0;j<G.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}printf("\n输入边的顶点和权值(如A B 1):\n"); //构造邻接矩阵for (k=0;k<G.arcnum;k++){scanf("%c %c %d",&v1,&v2,&w); //输入一条有向边的起点终点和权值i = LocateVex(G,v1); //确定顶点在G中的位置j = LocateVex(G,v2);G.arcs[i][j].adj = w;getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 }return OK;}（3）输出邻接矩阵函数Status PrintArcs( MGraph &G){int i;int j;printf("邻接矩阵\n"); //按行序依次输出for ( i = 0; i < G.vexnum; i++ ){for ( j = 0; j < G.vexnum; j++ ){if ( INFINITY == G.arcs[i][j].adj)printf("%6s%","INF");elseprintf("%6d",G.arcs[i][j]);}printf("\n");}return OK;}（4）最短路径函数Status ShortestPath_DIJ(MGraph G, int v0, int p[], int D[]){//求有向网G的V0到其余顶点的最短路径P[v]及其带权长度D[v]//若p[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点//final[v]为TRUE当且仅当v∈S，即已经求得从v0到v的最短路径int m,v,i,w,j,k;int min;int final[MAX_VERTEX_NUM];char a[MAX_VERTEX_NUM];for(v=0; v<G.vexnum; ++v){final[v] = FALSE;p[v]=FALSE;D[v] = G.arcs[v0][v].adj;}//forD[v0]=0; final[v0] = TRUE; //初始化，v0属于S//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集for(i=1;i<G.vexnum;++i){min = INFINITY;for(w=0;w<G.vexnum;++w)if(!final[w]) //w顶点在V-S中if(D[w]<min) {k=w; min = D[w];} //w离v0更近final[k] = TRUE;for(w=0; w<G.vexnum; ++w) //更新当前最短路径及距离if(!final[w]&&(min+G.arcs[k][w].adj <D[w])){D[w] = min + G.arcs[k][w].adj;p[w] =k;}//if}//forprintf("dijkstra(%c): \n", G.vexs[v0]);for (i = 0; i < G.vexnum; i++){printf(" 最短路径长度(%c, %c)=%d\n", G.vexs[v0], G.vexs[i], D[i]);printf(" 最短路径为：");m=i;j=0;while (m!=v0){a[j]=G.vexs[m];m=p[m];j++;}a[j]=G.vexs[v0];for (m=j;m>=0;m--){printf("%c ", a[m]);}printf("\n");}return OK;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）四、实验程序代码(该部分请加注释)#include "stdio.h"#include "stdlib.h"#include "malloc.h"#include <limits.h>#define OK 1#define TRUE 1#define FALSE 0#define INFINITY 65535 //最大值无穷#define MAX_VERTEX_NUM 40 //最大顶点个数typedef int InfoType;typedef int VRType;typedef char VertexType;typedef int Status;typedef struct ArcCell{VRType adj;InfoType *info; //该边相关信息的指针}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的顶点数和有向边数}MGraph;int LocateVex(MGraph &G,VertexType ch){//返回顶点在G中顶点向量中的下标值int i;for ( i = 0; G.vexnum; i++ )if ( ch == G.vexs[i] )return i;return -1;}Status CreateDG(MGraph &G){//创建有向图的邻接矩阵int i,j,k,w;char v1,v2;printf("请输入顶点数和边数：");scanf("%d%d",&G.vexnum,&G.arcnum);printf("\n请按次序输入%d个顶点字母标号(如ABCD等)：",G.vexnum); getchar(); //弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for (i=0;i<G.vexnum;i++)scanf("%c",&G.vexs[i]);getchar(); //弹出缓冲区中上次最后出入的换行符，即最后按下的回车键for (i=0;i<G.vexnum;++i) //初始化邻接矩阵for (j=0;j<G.vexnum;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}printf("\n输入边的顶点和权值(如A B 1):\n"); //构造邻接矩阵for (k=0;k<G.arcnum;k++){scanf("%c %c %d",&v1,&v2,&w); //输入一条有向边的起点终点和权值i = LocateVex(G,v1); //确定顶点在G中的位置j = LocateVex(G,v2);G.arcs[i][j].adj = w;getchar();//弹出缓冲区中上次最后出入的换行符，即最后按下的回车键 }return OK;}Status PrintArcs( MGraph &G){//输出邻接矩阵int i;int j;printf("邻接矩阵\n"); //按行序依次输出for ( i = 0; i < G.vexnum; i++ ){for ( j = 0; j < G.vexnum; j++ ){if ( INFINITY == G.arcs[i][j].adj)printf("%6s%","INF");elseprintf("%6d",G.arcs[i][j]);}printf("\n");}return OK;}Status ShortestPath_DIJ(MGraph G, int v0, int p[], int D[]){//求有向网G的V0到其余顶点的最短路径P[v]及其带权长度D[v]//若p[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点//final[v]为TRUE当且仅当v∈S，即已经求得从v0到v的最短路径int m,v,i,w,j,k;int min;int final[MAX_VERTEX_NUM];char a[MAX_VERTEX_NUM];for(v=0; v<G.vexnum; ++v){final[v] = FALSE;p[v]=FALSE;D[v] = G.arcs[v0][v].adj;}//forD[v0]=0; final[v0] = TRUE; //初始化，v0属于S//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集for(i=1;i<G.vexnum;++i){min = INFINITY;for(w=0;w<G.vexnum;++w)if(!final[w]) //w顶点在V-S中if(D[w]<min) {k=w; min = D[w];} //w离v0更近final[k] = TRUE;for(w=0; w<G.vexnum; ++w) //更新当前最短路径及距离if(!final[w]&&(min+G.arcs[k][w].adj <D[w])){D[w] = min + G.arcs[k][w].adj;p[w] =k;}//if}//forprintf("dijkstra(%c): \n", G.vexs[v0]);for (i = 0; i < G.vexnum; i++){printf("最短路径长度(%c, %c)=%d\n", G.vexs[v0], G.vexs[i], D[i]);printf(" 最短路径为：");m=i;j=0;while (m!=v0){a[j]=G.vexs[m];m=p[m];j++;}a[j]=G.vexs[v0];for (m=j;m>=0;m--){printf("%c ", a[m]);}printf("\n");}return OK;}void mainmenu() //输出菜单,供用户进行操作选择{printf("\n菜单");printf(" *1.创建有向图邻接矩阵 *\n");printf(" *2.输出邻接矩阵 *\n");printf(" *3.从某点开始到各点的最短路径*\n");printf(" *0.退出 *\n");}void main() // 主函数{MGraph G;int choose;int v0;int p[MAX_VERTEX_NUM]={0};int D[MAX_VERTEX_NUM]={0};while(1){mainmenu();printf("\n请输入你的选择：");scanf("%d",&choose);switch(choose){case 1://在此插入创建有向图邻接矩阵函数system("cls");CreateDG(G);system("PAUSE");system("cls");break;case 2://在此插入输出邻接矩阵函数system("cls");PrintArcs(G);printf("\n");system("PAUSE");system("cls");break;case 3://在此调用从某点开始从某点开始到各点的最短路径求解函数system("cls");printf("请输入开始结点：");scanf("%d",&v0);ShortestPath_DIJ(G,v0,p,D);system("PAUSE");system("cls");break;case 0://退出exit(0);break;default://输入非法，提示用户重新输入printf("\n输入错误，重新输入！\n");}}}。