Dijkstra最短路径.doc

福建农林大学计算机与信息学院(程序设计类课程)实验报告课程名称:数据结构姓名:吴秋月系:计算机专业:计算机科学与技术(专升本年级:2008级学号:081806111指导教师:黄思先职称:副教授福建农林大学计算机与信息学院实验报告系:计科(专升本)专业:计算机科学与技术年级:08级姓名:吴秋月学号:081806111实验室号:__田514计算机号:18实验三Dijkstra最短路径(验证性一、实验目的和要求1,掌握图的有关图相关操作算法2,熟悉图的基本存储方法3,了解掌握图的基本术语二、实验内容和原理实验内容:已知某交通网中,由站点(源点)出发到达等5个结点(终点)的可能路径如下有向连通网所示。编程计算和输出从出发到达其它5个结点的最短路径和路径的长度。实验原理:这是一个典型的单源点最短路径问题,可以利用Dijkstra算法求解。有向连通的交通网信息,可以采用带权的邻接矩阵存储。运用Dijkstra算法计算出各最短路径上每个终点的前驱站点以及各最短路径的长度,再利用栈通过回溯的方法输出最短路径。三、实验环境硬件环境:多媒体实验室学生用微机局域网环境软件环境:WindowsxpprofessionalTurboC/C++forwindows四、算法描述及实验步骤1,算法描述∞1635∞69∞∞∞28∞∞8∞∞∞191∞∞∞3∞510∞∞∞11∞∞∞∞∞7∞∞01161351∞1691∞101161351∞1691242011613513166912420116134431636424201161344316353242011613443163532421确定2确定6确定4确定3确定5确定2,算法描述及实验步骤在TurboC/C++,在编译窗口编写程序代码,若编译链接都通过,则运行程序,得出正确的结果,正确的程序代码及相关注释如下所示:#include""#include""#include""#defineN010//宏定义一个常量N0值#defineinfi32767//宏定义一个常量infi值typedefintAdjMatrix[N0+1][N0+1];ode{intv,w;//v表示顶点,odenext;}ode;typedefstructnode{intdegree;//ode*first;//ode的第一个指针}AdjList[N0+1];AdjMatrixadjmatrix;//定义一个整形二维数组adjmatrixAdjListadjlist;intn;//表示结点个数voidcreateAdj({inti,j,w,k;//w表示权值,ode*p;freopen("c:\\","r",stdin;//可用文件进行输入freopen("c:\\","w",stdout;//可用文件进行输出scanf("%d",&n;//输入个数nscanf("%d",&k;//K为0时是无向图,(i=1;i<=n;i++//初始化邻接矩阵for(j=1;j<=n;j++if(i==jadjmatrix[i][j]=0;//若i==把0赋给adjmatrix[i][j]elseadjmatrix[i][j]=infi;//若i!=j,把infimax赋给adjmatrix[i][j]do{scanf("%d%d%d",&i,&j,&w;//输入I,j,w的值if(i<1||i>n||j<1||j>n//若i、j不在所给的范围当中,就结束该循环break;adjmatrix[i][j]=w;//把w权值写入i行j列的邻接距阵里p=adjlist[i].first;//头指针指向pwhile(p&&p->v!=jp=p->next;if(pcontinue;p=(ode*malloc(sizeof(ode;//给p分配新空间p->v=j;p->w=w;//j赋给p的顶点,w赋给p的权值p->next=adjlist[i].first;//p的下一个结点指向adjlist[i]的头指针adjlist[i].first=p;//链表adjlist[i]的第一个指针在指向padjlist[j].degree++;if(k==0{adjmatrix[j][i]=w;p=(ode*malloc(sizeof(ode;//给p分配新空间p->v=i;p->w=w;//i赋给p的顶点,w赋给p的权值p->next=adjlist[j].first;//p的下一个结点指向adjlist[i]的头指针adjlist[j].first=p;//链表adjlist[i]的第一个指针在指向pa