1、 数据结构课程设计报告 学 院：信 息 科 学 技 术 学 院 题题 目目： 弗洛伊德算法与最短路径 一、课程设计题目 弗洛伊德算法与最短路径 二、用途简介 1、最短路径问题在生活中时常见到：比如，我们去某一地方，我们总是想知 道到达目的地的最短路径，或者是最短到达时间。 2、设计思路: 先用迪杰斯特拉算法，找到有向图中某一顶点到别的顶点的最短路径， 再 不断的调用我们刚刚写的迪杰斯特拉算法。最后输出任意两点之间的最短路径。 迪杰斯特拉算法的实现方法是，对于有向图采用邻接矩阵的方法存放。然 后建立两个数组，其中一个数组存放的是某一顶点到这点的最短路径的值。 另一 个数组定义为线性链表的表头单元
2、，然后再数组后面不断加入顶点路径。 再在迪 杰斯特拉算法内部设一个数组，用来标记顶点元素是否被访问。 每次在寻找权值 最小的且没有被访问过得顶点。 再加入新顶点后要修正那些还没有被访问的点的 权值。 三、测试数据： 测试数据表一： 0 50 10 Inf 45 Inf Inf 0 15 Inf 10 Inf 20 Inf 0 15 Inf Inf Inf 20 Inf 0 35 Inf Inf Inf Inf 30 0 Inf Inf Inf Inf 3 Inf 0 表一的顶点数据在数组中按下标从小到大存放的顺序为 abcdef。 测试数据表二： 0 4 Inf 12 0 5 6 Inf 0
3、表一的顶点数据在数组中按下标从小到大存放的顺序为 ABC。 四、概要设计 1、元素类型、结点类型和指针类型： typedef struct arcnode int adj; arcnode; typedef struct char vertexmax; arcnode arcsmaxmax; int vexnum,arcnum; matrix; typedef struct linknode char data; struct linknode *next; linklist; 2、建立一个头结点数组 pathmax,和最短路径数组 distmax: int distmax,i; linkli
4、st pathmax; 3、主函数和其他函数： void main() matrix g; creatdn( int distmax,i; linklist pathmax; for(i=1;ivexnum, for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) g-arcsij.adj=inf; printf(“%sn“,“顶点信息“); for(k=0;kvexnum;k+) scanf(“%c“, printf(“%sn“,“顶点 i 与 j 之间的权值“); for(k=1;karcnum;k+) scanf(“%d,%d,%d“, g-arcsij.adj=
5、weight; /printf(“%c“,g-vertex0); /printf(“%c“,g-vertex1); /printf(“%c“,g-vertex2); /printf(“%c“,g-vertex3); /printf(“%d“,g-arcs01); typedef struct linknode char data; struct linknode *next; linklist; void init(linklist *l) /l=(linklist*)malloc(sizeof(linknode); l-next=null; void link(linklist *p,cha
6、r x) linklist *q; q=(linklist*)malloc(sizeof(linknode); while(p-next!=null) p=p-next; /q-next=p-next; p-next=q; q-data=x; q-next=null; void shortestpath(matrix *g,int c,int distmax,linklist pathmax) printf(“顶点%d 到各个点的最短距离n“,c); int i,t,min,k; int smax=0; linklist *b; for(i=1;ivexnum;i+) init( disti=g-arcsci.adj; if(disti!=inf) link( link( sc=1; for(t=1;tvexnum-1;t+
