Dijkstra最短路径.doc

福建农林大学计算机与信息学院（程序设计类课程）实验报告课程名称：数据结构姓 名：吴秋月系：计算机专 业：计算机科学与技术(专升本)年 级：2008级学 号：081806111指导教师：黄思先职 称：副教授 福建农林大学计算机与信息学院实验报告系： 计科（专升本） 专业： 计算机科学与技术 年级： 08级 姓名： 吴秋月 学号： 081806111 实验室号：_田514 计算机号： 18 实验三 Dijkstra最短路径(验证性)一、 实验目的和要求1，掌握图的有关图相关操作算法2，熟悉图的基本存储方法3，了解掌握图的基本术语二、 实验内容和原理实验内容：已知某交通网中，由站点（源点）出发到达等5个结点（终点）的可能路径如下有向连通网所示。编程计算和输出从出发到达其它5个结点的最短路径和路径的长度。实验原理：这是一个典型的单源点最短路径问题，可以利用Dijkstra算法求解。有向连通的交通网信息，可以采用带权的邻接矩阵存储。运用Dijkstra算法计算出各最短路径上每个终点的前驱站点以及各最短路径的长度，再利用栈通过回溯的方法输出最短路径。三、 实验环境硬件环境：多媒体实验室学生用微机局域网环境软件环境:Windows xp professional Turbo C/C+ for windows 四、 算法描述及实验步骤 1，算法描述 16 35 69 28 8 19 1 3 5 10 11 7 0116135116911 011613511691242011613513166912420116134431636424201161344316353242011613443163532421确定 2确定 6确定 4确定 3确定 5确定2，算法描述及实验步骤在Turbo C/C+ for windows中新建的名为Dijkstra.c的C程序文件，在编译窗口编写程序代码，若编译链接都通过，则运行程序，得出正确的结果，正确的程序代码及相关注释如下所示：#include stdio.h#include conio.h#include alloc.h#define N0 10 /宏定义一个常量N0值#define infi 32767 /宏定义一个常量infi值typedef int AdjMatrixN0+1N0+1;typedef struct arcnode int v,w; /v表示顶点，w表示权值 struct arcnode next;ArcNode;typedef struct node int degree; /表示度 ArcNode *first; /指向ArcNode的第一个指针AdjListN0+1;AdjMatrix adjmatrix; /定义一个整形二维数组adjmatrixAdjList adjlist;int n; /表示结点个数 void createAdj() int i,j,w,k; / w表示权值，k表示是否的有向图还是无向图 ArcNode *p; freopen(c:dijkstra.in,r,stdin); /可用文件进行输入 freopen(c:dijkstra.out, w, stdout); /可用文件进行输出 scanf(%d,&n); /输入个数n scanf(%d,&k); /K为0时是无向图,为1是有向图. for(i=1;i=n; i+) /初始化邻接矩阵 for(j=1; j=n; j+) if(i=j) adjmatrixij=0; /若i=把0赋给adjmatrixij else adjmatrixij=infi; /若i!=j，把infimax赋给adjmatrixij do scanf(%d%d%d, &i,&j, &w); /输入I,j,w的值 if(in | jn) /若i、j不在所给的范围当中，就结束该循环 break; adjmatrixij=w; /把w权值写入i行j列的邻接距阵里 p=adjlisti.first; /头指针指向p while(p & p-v!=j ) p=p-next; if(p) continue; p=(ArcNode*)malloc(sizeof(ArcNode); /给p分配新空间 p-v=j; p-w=w; / j赋给p的顶点，w赋给p的权值 p-next=adjlisti.first; / p的下一个结点指向adjlisti的头指针 adjlisti.first=p; /链表adjlisti的第一个指针在指向p adjlistj.degree+; if(k=0) adjmatrixji=w; p=(ArcNode*)malloc(sizeof(ArcNode); /给p分配新空间 p-v=i; p-w=w; / i赋给p的顶点，w赋给p的权值 p-next=adjlistj.first; / p的下一个结点指向adjlisti的头指针 adjlistj.first=p; /链表adjlisti的第一个指针在指向p adjlisti.degree+; while(1);void dijkstra(int x) / 用dijkstra算法实现最短路径 int distN0+1, pathN0+1, markN0+1; /*定义3个数组，dist存储源点到个结点最短路径，path存储源点到当前结点路径上的倒数第2个点，mark存储的数为2时表示结点未确定，为1时表示结点已确定。*/ int i,j,k,min; for(i=1; i=n; i+) marki=2; /初始化mark为2，表示结点未确定 pathi=x; /初始化path为源点x disti=adjmatrixxi; / 源点x到各点的距离分别写入dist markx=1; /x已经确定 for(i=1; i=n-1; i+) min=infi; k=0; for(j=1; j=n; j+) /在为确定的结点里找出一个路径最短的 if( markj=2 & distjmin) min=distj;k=j; /k为最短路径的结点 markk=1; /k结点已经确定 for(j=1; jdistk+(long)adjmatrixkj) /如果未确定的结点j在经过刚已确定的结点k的路径比当前结点值小 distj=distk+adjmatrixkj; /*修改结点j的路径值，路径值为上一次已确定的结点k的路径值加上结点k到j的路径值 */pathj=k; /修改结点j的path值为上次已确定的k结点 for(i=1; i=n; i+) if(i!=x) /如果i不等于源点x printf(%d-, i); k=pathi; /k为源点到i路径上的倒数第2个结点 while(k!=x) / 当k不等于x ,循环输出 printf(%d-, k); k=pathk; /直到k为源点 printf(%d:%dn, k, disti); /输出源点和总路径值 main() clrscr(); /清屏 createAdj(); printf(nDijkstra:n); dijkstra(1); /源点为1，即从1开始。五、 调试过程调试表明调试通过，运行程序便可以得出正确结果。六、 实验结果输入相应的数据，得出结果，截图如下： 七、 总结通过这次试验，了