Dijkstra算法完整實現(xiàn)源代碼

Dijkstra算法的完整實現(xiàn)版本，算法的源代碼/*Dijkstra.cCopyright(c)2002,2006byctu_85AllRightsReserved.*/#include"stdio.h"#include"malloc.h"#definemaxium32767#definemaxver9/*definesthemaxnumberofvertexswhichtheprogrammcanhandle*/#defineOK1structPoint{charvertex[3];structLink*work;structPoint*next;};structLink{charvertex[3];intvalue;structLink*next;};structTable/*theworkbannchofthealgorithm*/{intcost;intKnown;charvertex[3];charpath[3];structTable*next;};intDijkstra(structPoint*,structTable*);intPrintTable(int,structTable*);intPrintPath(int,structTable*,structTable*);structTable*CreateTable(int,int);structPoint*FindSmallest(structTable*,structPoint*);/*Findthevertexwhichhasthesmallestvalueresideinthetable*/intmain(){inti,j,num,temp,val;charc;structPoint*poinpre,*poinhead,*poin;structLink*linpre,*linhead,*lin;structTable*tabhead;poinpre=poinhead=poin=(structPoint*)malloc(sizeof(structPoint));poin->next=NULL;poin->work=NULL;restart:printf("Notice:ifyouwannatoinputavertex,youmustusetheformatofnumber!\n");printf("Pleaseinputthenumberofpoints:\n");scanf("%d",&num);if(num>maxver||num<1||num%1!=0){printf("\nNumberofpointsexception!");gotorestart;}for(i=0;i<num;i++){printf("Pleaseinputthepointsnexttopoint%d,endwith0:\n",i+1);poin=(structPoint*)malloc(sizeof(structPoint));poinpre->next=poin;poin->vertex[0]='v';poin->vertex[1]='0'+i+1;poin->vertex[2]='\0';linpre=lin=poin->work;linpre->next=NULL;for(j=0;j<num-1;j++){printf("Thenumberofthe%dthvertexlinkedtovertex%d:",j+1,i+1);scanf("%d",&temp);if(temp==0){lin->next=NULL;break;}else{lin=(structLink*)malloc(sizeof(structLink));linpre->next=lin;lin->vertex[0]='v';lin->vertex[1]='0'+temp;lin->vertex[2]='\0';printf("Pleaseinputthevaluebetwixt%dthpointtowards%dthpoint:",i+1,temp);scanf("%d",&val);lin->value=val;linpre=linpre->next;lin->next=NULL;}poinpre=poinpre->next;poin->next=NULL;}printf("PleaseenterthevertexwhereDijkstraalgorithmstarts:\n");scanf("%d",&temp);tabhead=CreateTable(temp,num);Dijkstra(poinhead,tabhead);PrintTable(temp,tabhead);returnOK;structTable*CreateTable(intvertex,inttotal){structTable*head,*pre,*p;inti;head=pre=p=(structTable*)malloc(sizeof(structTable));p->next=NULL;for(i=0;i<total;i++){p=(structTable*)malloc(sizeof(structTable));pre->next=p;if(i+1==vertex){p->vertex[0]='v';p->vertex[1]='0'+i+1;p->vertex[2]='\0';p->cost=0;p->Known=0;}else{p->vertex[0]='v';p->vertex[1]='0'+i+1;p->vertex[2]='\0';p->cost=maxium;p->Known=0;}p->next=NULL;pre=pre->next;}returnhead;}intDijkstra(structPoint*p1,structTable*p2)/*Coreoftheprogramm*/

intcosts;chartemp;structPoint*poinhead=p1,*now;structLink*linna;structTable*tabhead=p2,*searc,*result;while(1){now=FindSmallest(tabhead,poinhead);if(now==NULL)break;result=p2;result=result->next;while(result!=NULL){if(result->vertex[1]==now->vertex[1])break;elseresult=result->next;}linna=now->work->next;while(linna!=NULL)/*updateallthevertexslinkedtothesignedvertex*/{temp=linna->vertex[1];searc=tabhead->next;while(searc!=NULL)thenew{if(searc->vertex[1]==temp)/*findthevertexlinkedtosignedvertexinthetableandupdate*/thenew{if((result->cost+linna->value)<searc->cost){searc->cost=result->cost+linna->value;/*setthevalue*/searc->path[0]='v';searc->path[1]=now->vertex[1];searc->path[2]='\0';}break;}elsesearc=searc->next;}linna=linna->next;}return1;}structPoint*FindSmallest(structTable*head,structPoint*poinhead){structPoint*result;structTable*temp;intmin=maxium,status=0;head=head->next;poinhead=poinhead->next;while(head!=NULL){if(!head->Known&&head->cost<min){min=head->cost;result=poinhead;temp=head;status=1;}head=head->next;poinhead=poinhead->next;}if(status){temp->Known=1;returnresult;}elsereturnNULL;}intPrintTable(intstart,structTable*head){structTable*begin=head;head=head->next;while(head!=NULL){if((head->vertex[1]-'0')!=start)PrintPath(start,head,begin);head=head->next;}returnOK;}intPrintPath(intstart,structTable*head,structTable*begin)structTable*temp=begin->next,*p,*t