#include#include#defineINT_MAX2147483647#defineINFINITYINT_MAX#defineFALSE0#defineTRUE1#defineNumVertices6/图中最大顶点个数typedefintPathMatrixNumVerticesNumVertices;/最短路径数组typedefintShortPathTableNumVertices;/最短路径长度typedefintAdjMatrixNumVerticesNumVertices;typedefcharVertexType;typedefstructVertexTypevexsNumVertices;AdjMatrixarcs;/邻接矩阵intvexnum,arcnum;MGraph;intLocateVex(MGraphG,charu);voidCreateMGraph(MGraph&G);voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D);intmain()intv0;charu;MGraphG;PathMatrixP;ShortPathTableD;printf(最短路径!n);CreateMGraph(G);printf(InputSource:);fflush(stdin);scanf(%c,&u);v0=LocateVex(G,u);ShortestPath_DIJ(G,v0,P,D);return0;/#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*#J*1初始化：S-v0;*Djarcs0j,j=1,2,，n-1;*/n为图中顶点个数*2求出最短路径的长度：*DkminDi,iWV-S;*SSUk;*3修改：*DiminDi,Dk+arcski,*对于每一个WV-S*4判断：若S=V,则算法结束，否则转2。voidShortestPath_DIJ(MGraphG,intv0,PathMatrix&P,ShortPathTable&D)/Dv为带权长度若Pvw为TRUE,则w是从v0到v当前求的最短路径上的顶点finalv为TRUE当且仅当VWV-S，即已经求得v0到V的最短路径finalv=TRUE也就是将v加入到SintfinalNumVertices;intw,v;/step1for(v=0;vG.vexnum;+v)finalv=FALSE;Dv=G.arcsv0v;for(w=0;wG.vexnum;+w)Pvw=FALSE;if(DvINFINITY)Pvv0=TRUE;Pvv=TRUE;/!finalw表示V-Sfor(inti=1;iG.vexnum;+i)/step4/step2intmin=INFINITY;for(w=0;wG.vexnum;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=TRUE;/step3for(w=0;wG.vexnum;+w)if(G.arcsvw!=INFINITY)if(!finalw&(min+G.arcsvwDw)Dw=min+G.arcsvw;for(intj=0;jG.vexnum;+j)Pwj=Pvj;Pww=TRUE;printf(n);printf(始点终点路径长度n);printf(n);printf(%c,G.vexsv0);for(w=0;wG.vexnum;+w)if(w!=0)printf();if(w=v0)printf(%cn,G.vexsw);elseif(Dw=INFINITY),G.vexsw);%dn,G.vexsw,Dw);n);printf(%cprintf(无n);elseprintf(%cprintf(intLocateVex(MGraphG,charu)inti;for(i=0;iG.vexnum;i+)if(u=G.vexsi)returni;if(i=G.vexnum)printf(Erroru!n);exit(1);return0;/建立邻接矩阵voidCreateMGraph(MGraph&G)inti,j,k,w;charv1,v2;/*printf(输入顶点数和边数:)；scanf(%d,%d,&G.vexnum,&G.arcnum);/printf(%d,G.vexnum)；printf(输入各个顶点名称:);fflush(stdin)；for(i=0;iG.vexnum;i+)scanf(%c,&G.vexsi);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij=INFINITY;for(k=0;kG.arcnum;k+)printf(输入每条边的起点、终点和权:n);fflush(stdin);scanf(%c,%c,%d,&v1,&v2,&w);/printf(%c,%c,%d,v1,v2,w);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcsij=w;*/G.vexnum=6;G.arcnum=10;for(i=0;iG.vexnum;i+)G.vexsi=0+i;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsij=INFINITY;G.arcs02=10;G.arcs04=30;G.arcs05=100;G.arcs12=5;G.arcs23=50;G.arcs35=10;G.arcs43=20;G.arcs45=60;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)if(G.arcsij!=INFINITY)printf(%4d,G.arcsij);elseprintf(%4d,0);if(j%G.vexnum=G.vexnum-1)printf(n);return;