数据结构 狄克斯特拉算法

1、数据结构上机报告名称：狄克斯特拉算法姓 名：学 号： 310班 级：计算101实验日期：2012.11.22指导教师：问题描述:带权图中从一个结点到另一个结点可能存在着多条路径，带权路径长度值最小的那条路 径称为最短路径，狄克斯特拉提出了一个按路径长度递增的顺序逐步产生最短路径的构造算法。用狄克斯特拉算法编一个程序求带权图的最短路径。如下图是一个有向带权图及其邻接 矩阵。该带权图从结点A到结点D有三条路径，分别为路径(A,D)，其带权路径长度为30； 路径(A,C,F,D),其带权路径长度为22；路径(A,C,B,E,D)，其带权路径长度为32。路径(A,C,F,D) 称为最短路径，其带权路径

2、长度22称为最短距离。0853088208888815088788808888840888810180基本要求：1.测试数据由用户在程序中给出。在狄克斯特拉函数设计中把函数设计成一个循环迭代过程。输入边信息数据时，以其在邻接矩阵的(行下标，列下标，权值)形式输入。要求输出固定结点到各结点的最短距离和最短路径的前一结点。测试数据：结点：a=A,B,C,D,E,F;边：rcw=0,2,5,0,3,30,1,0,2,1,4,8,2,1,15,2,5,7,4,3,4, 5,3,10,5,4,18;算法思想：设计两个结点的集合S和T，集合S中存放已找到最短路径的结点，集合T 中存放当前还未找到最短路径的

3、结点。初始状态时，集合S中只包含源点，设为 v0，然后不断从集合T中选择到源点v0路径长度最短的结点u加入到集合S中， 集合S中每加入一个新的结点u都要修改从源点v0到集合T中剩余结点的当前 最短路径长度值，集合T中各结点的新的当前最短路径长度值，为原来的最短 路径长度值与从源点过结点u到达该结点的路径长度中的较小者。此过程不断重 复，直到集合T中的结点全部加入到集合S中为止。模块划分：.文件SeqList.h”，用于下文件“AMGraph.h”，其中包括顺序表的初始化、求 当前数据元素个数、插入、删除、取数据元素操作；.文件“AMGraph.h”，有初始化、插入结点、插入边、删除边、删除结点

4、、寻 找邻接结点和邻接结点的下一邻接结点的操作；.文件AMGraphC.h”，用于图的创建；(4).文件“Dijkstra.h”，狄克斯特拉函数的设计；(5).文件“Main.c”，输出结点A到其他结点的最短距离和最短路径的前一结点。数据结构：1)线性表数据结构：typedef structDataType listMaxSize;int size;SeqList;图的数据结构：typedef structSeqList Vertices;/*存放结点的顺序表*/int edgeMaxVerticesMaxVertices;/* 存放边的邻接矩阵 */int numOfEdges;/* 边的条

5、数*/AMGraph;/*图的结构体定义*/边的数据结构typedef structint row;/*行下标 */int col;/* 列下标 */int weight;/* 权值 */RowColWeight;/*边信息结构体定义*/源程序：文件 eqLisLh”/*定义结构体*/typedef struct(DataType listMaxSize;int size;SeqList;/*初始化*/void ListInitiate(SeqList *L)(L-size=0;/*求当前数据元素个数*/int ListLength(SeqList L)(return L.size;/*插入数

6、据元素*/int ListInsert(SeqList *L,int i,DataType x)(int j;if(L-size=MaxSize)(printf（顺序表已满无法插入！n）;return 0;else if(iL-size)(printf(参数1不合法！n);return 0;else(/*为插入做准备*/for(j=L-size;ji;j-) L-listj=L-listj-1;L-listi=x;/*插入 x*/L-size+;/*元素个数加*/return 1; /*删除数据元素*/int ListDelete(SeqList *L,int i,DataType *x)(i

7、nt j;if(L-size=0)(printf(顺序表已空无数据元素可删！n);return 0;else if(iL-size-1)(printf(参数1不合法);return 0;else(*x=L-listi;/*保存删除的元素到乂中*/*依次前移*/for(j=i+1;jsize-1;j+) L-listj-1=L-listj;L-size-;/*数据元素个数减*/return 1; /*取数据元素*/int ListGet(SeqList L,int i,DataType *x)/*取顺序表L中第i个数据元素存于x中，成功返回，失败返回*/if(iL.size-1)(printf(

8、参数1不合法！n);return 0;else(*x=L.listi;return 1;文件” AMGraph.h”#includeSeqList.h/*包含顺序表头文件*/typedef struct(SeqList Vertices; /*存放结点的顺序表*/int edgeMaxVerticesMaxVertices;/* 存放边的邻接矩阵 */int numOfEdges;/* 边的条数*/AMGraph;/*图的结构体定义*/void Initiate(AMGraph *G,int n) /*初始化*/(int i,j;for(i=0;in;i+)for(j=0;jedgeij=0;

9、else G-edgeij=MaxWeight;G-numOfEdges=0;/* 边的条数置为 0*/ListInitiate(&G-Vertices); /* 顺序表初始化 */void InsertVertex(AMGraph *G,DataType vertex)/*在图G中插入结点vertex*/(ListInsert(&G-Vertices,G-Vertices.size,vertex);/*顺序表尾插入*/void InsertEdge(AMGraph *G,int v1,int v2,int weight)/*在图G中插入边,边的权为weight*/(if(v1G-Vertic

10、es.size|v2G-Vertices.size)(printf(参数v1或v2越界出错！n);exit(1);G-edgev1v2=weight;G-numOfEdges+;void DeleteEdge(AMGraph *G,int v1,int v2)/*在图G中删除边*/(if(v1G-Vertices.size|v2G-Vertices.size|v1=v2)(printf(参数v1或v2越界出错！n);exit(1);if(G-edgev1v2=MaxWeight|v1=v2)(printf(该边不存在！n);exit(0);G-edgev1v2=MaxWeight;G-numO

11、fEdges-;void DeleteVertex(AMGraph *G,int v)/*删除结点v*/(int n=ListLength(G-Vertices),i,j;DataType x;for(i=0;in;i+)/*计算删除后的边数*/for(j=0;jedgeij0&G-edgeijnumOfEdges-; /* 计算被删除边 */for(i=v;in;i+) /* 删除第行*/for(j=0;jedgeij=G-edgei+1j;for(i=0;in;i+) /* 删除第列*/for(j=v;jedgeij=G-edgeij+1;ListDelete(&G-Vertices,v,

12、&x); /* 删除结点 v*/int GetFirstVex(AMGraph G,int v)/*在图G中寻找序号为v的结点的第一个邻接结点*/*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/(int col;if(vG.Vertices.size)(printf(参数v1越界出错！n);exit(1);for(col=0;col0&G.edgevcolMaxWeight) return col; return -1;int GetNextVex(AMGraph G,int v1,int v2)/*在图G中寻找V1结点的邻接结点v2的下一个邻接结点*/*如果这样的邻接结点存

13、在，返回该邻接结点的序号；否则，返回-1*/*v1和v2都是相应结点的序号*/(int col;if(v1G.Vertices.size|v2G.Vertices.size)(printf(参数v1或V2越界出错！n);exit(1);for(col=v2+1;col0&G.edgev1colMaxWeight) return col; return -1;文件” AMGraphC.h”typedef struct(int row;/*行下标*/int col; /* 列下标 */int weight;/* 权值 */RowColWeight;/*边信息结构体定义*/void CreatGra

14、ph(AMGraph *G,DataType V,int n,RowColWeight E,int e)/*在图G中插入n个结点信息V和e条边信息E*/(int i,k;Initiate(G,n);/*结点顺序表初始化*/for(i=0;in;i+)InsertVertex(G,Vi);/* 结点插入*/for(k=0;ke;k+)InsertEdge(G,Ek.row,Ek.col,Ek.weight); /* 边插入*/文件 ”Dijkstra.h”void Dijkstra(AMGraph G,int v0,int distance口，int path)/*带权图G从下标v0结点到其他结

15、点的最短距离diatance*/*和最短路径下标path*/(int n=G.Vertices.size;int *s=(int *)malloc(sizeof(int)*n);int minDis,i,j,u;/*初始化*/for(i=0;in;i+)(distancei=G.edgev0i;si=0;if(i!=v0&distanceiMaxWeight)pathi=v0;else pathi=-1;sv0 = 1;/*标记结点v0已从集合丁加入集合，中*/*在当前还未找到最短路径的结点集中选取具有最短距离的结点u*/for(i=1;in;i+)(minDis=MaxWeight;for(

16、j=0;jn;j+)if(sj=0&distancejminDis)(u=j;minDis二distancej;/*当已不存在；路径时算法结束；此语句对非连通图是必须的*/ if(minDis=MaxWeight) return;su = 1;/*标记结点u已从集合T中加入到集合，中*/*修改从v0到其他结点的最短路径*/for(j=0;jn;j+)if(sj=0&G.edgeujMaxWeight&distanceu+G.edgeujdist ancej)(/*结点v0经结点u到其他结点的最短距离和最短路径*/distancej=distanceu+G.edgeuj;pathj=u;文件 ”

17、Main.c”#include#include#includetypedef char DataType;#define MaxSize 100#define MaxVertices 10#define MaxWeight 10000#includeAMGraph.h”#includeAMGraphC.h#includeDijkstra.h”void main(void)AMGraph g;char a=A,B,C,D,E,F;RowColWeightrcw=0,2,5,0,3,30,1,0,2,1,4,8,2,1,15,2,5,7,4,3,4,5,3,10,5,4,18;int i,n=6,e=9;int distance6,path6;CreatGraph(&g,a,n,rcw,e);Dijkstra(g,0,distance,path);printf(从结点c到其他各结点的最短距离为:n,g.Vertices.list0);for(i=0;in;i+)printf(到结点c 的最短距离%d:n,g.Vertices.listi,distancei);print