图的最短路应用的算法.doc

《图的最短路应用的算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//定义状态代码及数据类型#defineNULL0#defineOK1#defineERROR0#defineINFINITY255#defineMAX_VERTEX_NUM20typedefintStatus;typedefintElemType;//-----------------------队列结构-------------------------//节点存储结构typedefstructQNode{ElemTypedata;structQNode*next;}QNode,*QueuePtr;//队列typedefstruct{QueuePtrfront;QueuePtrre

2、ar;}LinkQueue;//初始化队列StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=newQNode;if(!Q.front)returnERROR;Q.front->next=NULL;returnOK;}//入队StatusEnQueue(LinkQueue&Q,ElemTypee){QueuePtrp=NULL;p=newQNode;if(!p)returnERROR;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}//出队StatusDeQueue(LinkQueu

3、e&Q,ElemType&e){QueuePtrp=NULL;if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)//注意当出队后为空队的情况Q.rear=Q.front;deletep;returnOK;}//判断是否为空队列StatusEmptyQueue(LinkQueue&Q){returnQ.front==Q.rear?true:false;}//复制队列(copyQ1toQ2)StatusCopyQueue(LinkQueue&Q1,Link

4、Queue&Q2){inte;QueuePtrp;while(!EmptyQueue(Q2)){//cleanQ2DeQueue(Q2,e);}//copyonebyonep=Q1.front->next;while(p){e=p->data;p=p->next;EnQueue(Q2,e);}returnOK;}图的结构－邻接矩阵//----------------------图的结构：邻接矩阵--------------------------////邻接矩阵元素typedefstructArcCell{intadj;//arcvalue:>0,INFINITY:nolinkcha

5、r*info;}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图的结构typedefstruct{charvexs[MAX_VERTEX_NUM][5];//顶点数组AdjMatrixarcs;//邻接矩阵intvexnum;//图当前的顶点数intarcnum;//图当前边的个数}MGraph;//建立邻接图（key=1为有向网，key=0为无向网）StatuscreateUDN(MGraph&G,intvexnum,intedgenum,char*names,char*edges,intkey){inti,j,k,valu

6、e;//输入当前图的顶点数，边个数G.vexnum=vexnum;G.arcnum=edgenum;//各个顶点数据for(i=0;i

7、r(k=0;k