《Dijkstra算法原理详细讲解.pdf》由会员分享，可在线阅读，更多相关《Dijkstra算法原理详细讲解.pdf（9页珍藏版）》请在三一文库上搜索。
1、Dijkstra算法原理详细讲解 如下图，设 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:时输入算法的起 始点 比如计算结果 v1v
2、4v2 表示从点 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 cha
3、r vertex3; struct Link *work; struct Point *next; ; struct Link char vertex3; int value; struct Link *next; ; struct Table /*the workbannch of the algorithm*/ int cost; int Known; char vertex3; char path3; struct Table *next; ; int Dijkstra(struct Point *,struct Table *); int PrintTable(int,struct T
4、able *); 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,*po
5、in; 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); sc
6、anf(%d, if(nummaxver|num1|num%1!=0) printf(nNumber of 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=(struct Link *)malloc(sizeof(struct Link); linpre-next=lin; lin-
7、vertex0=v; lin-vertex1=0+temp; lin-vertex2=0; printf(Please input the value betwixt %d th point towards %d th point:,i+1,temp); scanf(%d, lin-value=val; linpre=linpre-next; lin-next=NULL; poinpre=poinpre-next; poin-next=NULL; printf(Please enter the vertex where Dijkstra algorithm starts:n); scanf(%
8、d, tabhead=CreateTable(temp,num); Dijkstra(poinhead,tabhead); PrintTable(temp,tabhead); return OK; struct Table * CreateTable(int vertex,int total) struct Table *head,*pre,*p; int i; head=pre=p=(struct Table *)malloc(sizeof(struct Table); p-next=NULL; for(i=0;inext=p; if(i+1=vertex) p-vertex0=v; p-v
9、ertex1=0+i+1; p-vertex2=0; p-cost=0; p-Known=0; else p-vertex0=v; p-vertex1=0+i+1; p-vertex2=0; p-cost=maxium; p-Known=0; p-next=NULL; pre=pre-next; return head; int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/ int costs; char temp; struct Point *poinhead=p1,*now; struct Lin
10、k *linna; struct Table *tabhead=p2,*searc,*result; while(1) now=FindSmallest(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 all the vertexs link
11、ed to the signed vertex*/ temp=linna-vertex1; searc=tabhead-next; while(searc!=NULL) if(searc-vertex1=temp)/*find the vertex linked to the signed vertex in the table and update*/ if(result-cost+linna-value)cost) searc-cost=result-cost+linna-value;/*set the new value*/ searc-path0=v; searc-path1=now-
12、vertex1; searc-path2=0; break; else searc=searc-next; linna=linna-next; return 1; struct Point * FindSmallest(struct Table *head,struct Point *poinhead) struct Point *result; struct Table *temp; int min=maxium,status=0; head=head-next; poinhead=poinhead-next; while(head!=NULL) if(!head-Known result=
13、poinhead; temp=head; status=1; head=head-next; poinhead=poinhead-next; if(status) temp-Known=1; return result; else return NULL; int PrintTable(int start,struct Table *head) struct Table *begin=head; head=head-next; while(head!=NULL) if(head-vertex1-0)!=start) PrintPath(start,head,begin); head=head-next; return OK; int PrintPath(int start,struct Table *head,struct Table *begin) struct Table *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); return OK;