1、Dijkstra算法原理详细讲解 如下图，设 A 为源点，求 A 到其他各顶点 （B、C、D、E、F）的最短路径。 线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶 点间的距离与图中的目视长度不能一一对等） 算法执行步骤如下表： Dijkstra算法的完整实现版本之算法的源代码 样例图: 输入格式: 输出格式: 输入时，将 s,t,x,y,z 五个点按照 1,2,3,4,5 起别名，输入格式按照下图例所示 当提示 Please enterthe vertexwhere Dijkstraalgorithmstarts:时输入算法的起 始点 比如计算结果 v1v4v2 表示从
2、点 1 到点 2 经过 1，4，2 为最短路径 Dijkstra 算法的完整实现版本，算法的源代码 /*Dijkstra.c Copyright (c)2002, 2006by ctu_85 AllRights Reserved. */ #includestdio.h #include malloc.h #definemaxium 32767 #definemaxver 9 /*definesthe max number of vertexswhichtheprogramm canhandle*/ #define OK 1 structPoint char vertex3; structLin
3、k *work; structPoint *next; ; structLink char vertex3; intvalue; structLink *next; ; structTable /*theworkbannch of thealgorithm*/ int cost; int Known; char vertex3; char path3; structTable *next; ; intDijkstra(structPoint *,struct Table *); intPrintTable(int,struct Table *); int PrintPath(int,struc
4、tTable *,struct Table *); structTable *CreateTable(int,int); structPoint * FindSmallest(structTable *,struct Point *);/*Find the vertexwhich has the smallestvalue resideinthe table*/ intmain() inti,j,num,temp,val; char c; structPoint *poinpre,*poinhead,*poin; structLink *linpre,*linhead,*lin; struct
5、Table *tabhead; poinpre=poinhead=poin=(structPoint *)malloc(sizeof(structPoint); poin-next=NULL; poin-work=NULL; restart: printf(Notice:ifyouwanna toinput avertex,you must use the format of number!n); printf(Please input thenumber of points:n); scanf(%d, if(nummaxver|num1|num%1!=0) printf(nNumber of
6、 points exception!); goto restart; for(i=0;inext=poin; poin-vertex0=v; poin-vertex1=0+i+1; poin-vertex2=0; linpre=lin=poin-work; linpre-next=NULL; for(j=0;jnext=NULL; break; else lin=(structLink *)malloc(sizeof(structLink); linpre-next=lin; lin-vertex0=v; lin-vertex1=0+temp; lin-vertex2=0; printf(Pl
7、ease input the valuebetwixt %dth point towards %dth point:,i+1,temp); scanf(%d, lin-value=val; linpre=linpre-next; lin-next=NULL; poinpre=poinpre-next; poin-next=NULL; printf(Pleaseenter thevertexwhereDijkstra algorithmstarts:n); scanf(%d, tabhead=CreateTable(temp,num); Dijkstra(poinhead,tabhead); P
8、rintTable(temp,tabhead); returnOK; structTable * CreateTable(intvertex,int total) structTable *head,*pre,*p; int i; head=pre=p=(structTable *)malloc(sizeof(structTable); p-next=NULL; for(i=0;inext=p; if(i+1=vertex) p-vertex0=v; p-vertex1=0+i+1; p-vertex2=0; p-cost=0; p-Known=0; else p-vertex0=v; p-v
9、ertex1=0+i+1; p-vertex2=0; p-cost=maxium; p-Known=0; p-next=NULL; pre=pre-next; returnhead; intDijkstra(structPoint *p1,struct Table *p2) /*Core of the programm*/ intcosts; char temp; structPoint *poinhead=p1,*now; structLink *linna; structTable *tabhead=p2,*searc,*result; while(1) now=FindSmallest(
10、tabhead,poinhead); if(now=NULL) break; result=p2; result=result-next; while(result!=NULL) if(result-vertex1=now-vertex1) break; else result=result-next; linna=now-work-next;while(linna!=NULL) /*update allthe vertexslinkedto thesigned vertex*/ temp=linna-vertex1; searc=tabhead-next; while(searc!=NULL
11、) if(searc-vertex1=temp)/*findthe vertexlinked tothe signedvertexinthe tableand update*/ if(result-cost+linna-value)cost) searc-cost=result-cost+linna-value;/*setthe new value*/ searc-path0=v; searc-path1=now-vertex1; searc-path2=0; break; else searc=searc-next; linna=linna-next; return1; structPoin
12、t * FindSmallest(structTable *head,struct Point *poinhead) structPoint *result; structTable *temp; intmin=maxium,status=0; head=head-next; poinhead=poinhead-next; while(head!=NULL) if(!head-Known result=poinhead; temp=head; status=1; head=head-next; poinhead=poinhead-next; if(status) temp-Known=1; r
13、eturnresult; else returnNULL; int PrintTable(int start,struct Table *head) structTable *begin=head; head=head-next; while(head!=NULL) if(head-vertex1-0)!=start) PrintPath(start,head,begin); head=head-next; returnOK; int PrintPath(int start,struct Table *head,structTable *begin) structTable *temp=begin-next,*p,*t; p=head; t=begin; if(p-vertex1-0)!=start PrintPath(start,temp,t); printf(%s,p-vertex); else if(p!=NULL) printf(n%s,p-vertex); returnOK;
