Dijkstra最短路径

1、福建农林大学计算机与信息学院（程序设计类课程）实验报告课程名称：数据结构姓 名：吴秋月系：计算机专 业：计算机科学与技术(专升本年 级：2008级学 号：081806111指导教师：黄思先职 称：副教授福建农林大学计算机与信息学院实验报告系： 计科（专升本） 专业： 计算机科学与技术 年级： 08级 姓名： 吴秋月 学号： 081806111 实验室号：_田514 计算机号： 18 实验三 Dijkstra最短路径(验证性一、 实验目的和要求1，掌握图的有关图相关操作算法2，熟悉图的基本存储方法3，了解掌握图的基本术语二、 实验内容和原理实验内容：已知某交通网中，由站点（源点）出发到达等5个结

2、点（终点）的可能路径如下有向连通网所示。编程计算和输出从出发到达其它5个结点的最短路径和路径的长度。实验原理：这是一个典型的单源点最短路径问题，可以利用Dijkstra算法求解。有向连通的交通网信息，可以采用带权的邻接矩阵存储。运用Dijkstra算法计算出各最短路径上每个终点的前驱站点以及各最短路径的长度，再利用栈通过回溯的方法输出最短路径。三、 实验环境硬件环境：多媒体实验室学生用微机局域网环境软件环境:Windows xp professionalTurbo C/C+ for windows 四、 算法描述及实验步骤1，算法描述 16 35 69 28 8 19 1 3 5 10 11

3、7 0116135116911 011613511691242011613513166912420116134431636424201161344316353242011613443163532421确定 2确定 6确定 4确定 3确定 5确定2，算法描述及实验步骤在Turbo C/C+ for windows中新建的名为Dijkstra.c的C程序文件，在编译窗口编写程序代码，若编译链接都通过，则运行程序，得出正确的结果，正确的程序代码及相关注释如下所示：#include "stdio.h"#include "conio.h"#include &quo

4、t;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; /定义一个整形二维数组adjmatrixAdjLi

5、st 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; /输入个数nscanf("%d",&k; /K为0时是无向图,为1是有向图

6、.for(i=1;i<=n; i+ /初始化邻接矩阵for(j=1; j<=n; j+if(i=j adjmatrixij=0; /若i=把0赋给adjmatrixijelse adjmatrixij=infi; /若i!=j，把infimax赋给adjmatrixijdo scanf("%d%d%d", &i,&j, &w; /输入I,j,w的值if(i<1 | i>n | j<1 | j>n /若i、j不在所给的范围当中，就结束该循环break;adjmatrixij=w; /把w权值写入i行j列的邻接距阵里p

7、=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=(ArcNod

8、e*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存储源点到当前结

9、点路径上的倒数第2个点，mark存储的数为2时表示结点未确定，为1时表示结点已确定。*/int i,j,k,min; for(i=1; i<=n; i+ marki=2; /初始化mark为2，表示结点未确定pathi=x; /初始化path为源点xdisti=adjmatrixxi; / 源点x到各点的距离分别写入distmarkx=1; /x已经确定for(i=1; i<=n-1; i+ min=infi;k=0;for(j=1; j<=n; j+ /在为确定的结点里找出一个路径最短的if( markj=2 && distj min=distj;k=j;

10、/k为最短路径的结点markk=1; /k结点已经确定for(j=1; j<=n; j+ if( markj=2 &&distj>distk+(longadjmatrixkj /如果未确定的结点j在经过刚已确定的结点k的路径比当前结点值小 distj=distk+adjmatrixkj; /*修改结点j的路径值，路径值为上一次已确定的结点k的路径值加上结点新教师姓名到 j 的路径值 */ pathj=k; /修改结点j的path值为上次已确定的k结点for(i=1; i<=n; i+ if(i!=x如果i不等于源点x printf("%d<-", i; k=pathi;为源点到i路径上的倒数第2班风建设while(k!=x / 当k不等于循环输出见附件k=pathk; /直到kprintf("%d:%dn", k, disti; /见附件main(clrscr(; /清屏createAdj(; printf("nDijkstra:n"dijkstra(1; /源点为1，即从1开始。五、 调试过程调试表明调试通过，运行程序便可以得出正确结果。六、 实验结果输入相应的数据，得出结果，截图如下： 七、