Dijkstra算法原理详细讲解.doc

详细讲解 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）算法执行步骤如下表： ? Dijkstra算法的完整实现版本之算法的源代码 样例图: 输入格式: 输出格式: 输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示 当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点 比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径 Dijkstra算法的完整实现版本，算法的源代码 /*?Dijkstra.c ??? Copyright (c) 2002, 2006 by ctu_85 ??? All Rights Reserved. */ #include stdio.h #include malloc.h #define maxium 32767 #define maxver 9 /*defines the max number of vertexs which the programm can handle*/ #define OK 1 struct Point { ?????? char vertex[3]; ?????? struct Link *work; ?????? struct Point *next; }; struct Link { ?????? char vertex[3]; ?????? int value; ?????? struct Link *next; }; struct Table /*the workbannch of the algorithm*/ { ?????? int cost; ?????? int Known; ?????? char vertex[3]; ?????? char path[3]; ?????? struct Table *next; }; int Dijkstra(struct Point *,struct Table *); int PrintTable(int,struct Table *); int PrintPath(int,struct Table *,struct Table *); struct Table * CreateTable(int,int); struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/ int main() { ?????? int i,j,num,temp,val; ?????? char c; ?????? struct Point *poinpre,*poinhead,*poin; ?????? struct Link *linpre,*linhead,*lin; ?????? struct Table *tabhead; ?????? poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point)); ?????? poin-next=NULL; ?????? poin-work=NULL; ?????? restart: ?????? printf(Notice:if you wanna to input a vertex,you must use the format of number!\n); ?????? printf(Please input the number of points:\n); ?????? scanf(%d,num); ?????? if(nummaxver||num1||num%1!=0) ?????? { ????????????? printf(\nNumber of points exception!); ????????????? goto restart; ?????? } ?????? for(i=0;inum;i++) ?????? { ????????????? printf(Please input the points next to point %d,end with 0:\n,i+1); ????????????? poin=(struct Point *)malloc(sizeof(struct Point)); ????????????