《Dijkstra算法求最短路径》由会员分享，可在线阅读，更多相关《Dijkstra算法求最短路径（8页珍藏版）》请在金锄头文库上搜索。
1、Dijkstra算法求最短路径（C#版）行如下图的路径，（vo是中心）:经过该算法后转化为下图usingSystem;usingSystem.Collections;usingSystem.Text;namespaceGreedyclassMarxprivateintdistance;privateintrow;privateArrayListways=newArrayList();publicMarx(intn,paramsintd)this.row=n;distance=newintrow*row;for(inti=0;irow*row;i+)this.distancei=di;for(i
2、nti=0;ithis.row;i+)/有row个点，则从中心到各点的路有row-1条ArrayListw=newArrayList();intj=0;w.Add(j);ways.Add(w);/publicvoidFind_way()ArrayListS=newArrayList(1);ArrayListSr=newArrayList(1);intIndexof_distance=newintthis.row;for(inti=0;irow;i+)Indexof_distancei=i;S.Add(Indexof_distance0);for(inti=0;i0)/假定中心点的编号是0的贪吃
3、法求路径for(inti=0;irow;i+)Di=this.distancei;intmin_num=(int)Sr0;/距中心点的最小距离点编号foreach(intsinSr)s;if(DsDmin_num)min_num=/以上可以排序优化S.Add(min_num);Sr.Remove(min_num);/把最新包含进来的点也加到路径中);(ArrayList)waysmin_num).Add(min_num/foreach(intelementinSr)intposition=element*(this.row)+min_num;boolexchange=false;/有交换标志i
4、f(DelementDmin_num+this.distanceposition)Delement=Delement;elseDelement=this.distanceposition+Dmin_num;exchange=true;/修改距离矩阵this.distanceelement=Delement;position=element*this.row;this.distanceposition=Delement;/修改路径if(exchange=true)(ArrayList)wayselement).Clear();foreach(intpointin(ArrayList)waysmi
5、n_num)(ArrayList)wayselement).Add(point);-Count;/publicvoidDisplay()/中心到各点的最短路径Console.WriteLine(中心到各点的最短路径如下：nn);intsum_d_index=0;foreach(ArrayListmotherinways)foreach(intchildinmother)Console.Write(V0-,child+1);Console.WriteLine(路径长0,distancesum_d_index+);classMainEnterPointstaticvoidMain(stringar
6、gs)intr;/列数Console.Write(请输入点个数(含配送中心点)：)；Int32.TryParse(Console.ReadLine(),outr);Console.WriteLine(各点分别为：n);for(inti=0；ir；i+)Console.Write(V0,i);Console.Write(假定第一个点是配送中心);Console.WriteLine(nn输入各点之间的距离(无通径的用个大整数表示八n)；inta=newintr*r;intda;for(inti=0;ir;i+)for(intj=i+1;jr;j+)距离是：,i,j);e(),outda);矩阵，阵
7、)Console.Write(V0到V1的Int32.TryParse(Console.ReadLinai*r+j=da;Console.WriteLine();/完善距离矩阵(距离矩阵其实可以是个上三角/但为了处理方便，还是将其完整成一个对称for(inti=0;ir;i+)for(intj=0;jr;j+)if(i=j)ai*r+j=0;aj*r+i=ai*r+j;Marxm=newMarx(r,a);Console.WriteLine();m.Find_way();m.Display();/该程序不但能够算出从中心到各点的最短路径距离,而且把路径也保存了下来.dijkstra最短路径问题
8、# include# include# definemaxlen10# definelarge999typedefstructintvexnum;charvexsmaxlen;intarcsmaxlenmaxlen;graph;voidinit_graph(graph*g)inti=0,j=0;g-vexnum=5;for(i=0;i5;i+)for(j=0;jarcsij=1000;g-arcs01=1;g-arcs03=3;g-arcs04=7;g-arcs12=2;g-arcs23=2;g-arcs24=2;g-arcs34=5;g-arcs32=3;g-arcs31=1;g-vexs0
9、=a;g-vexs1=b;g-vexs2=c;g-vexs3=d;g-vexs4=e;voidshortpath_dijkstra(graphg)intcostmaxlenmaxlen;/costij:Thecostofitoj.intdistmaxlen;/disti:Thedistanceofsourcepointtoi.intpathmaxlen;/Thepointpassedby.intsmaxlen;/ifsi=1,theniisinthesourcepointgather.inti,j,n,v0,min,u;printf(Inputthesourcepoint(1meansthef
10、irstpoint):);scanf(%d,&v0);v0-;for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+)costij=g.arcsij;for(i=0;ig.vexnum;i+)disti=costv0i;if(disti0)pathi=v0;si=0;sv0=1;for(i=0;ig.vexnum;i+)min=large;u=v0;for(j=0;jg.vexnum;j+)if(sj=0&distjmin)min=distj;u=j;su=1;for(j=0;jg.vexnum;j+)if(sj=0&distu+costujdistj)distj=
11、distu+costuj;pathj=u;printf(Outputn,v0);for(i=0;ig.vexnum;i+)if(si=1)u=i;while(u!=v0)printf(%c-,g.vexsu);u=pathu;printf(%c,g.vexsu);printf(:%dn,disti);elseprintf(%c-%c:nopathn,g.vexsi,g.vexsv0);intmain()graphg;init_graph(&g);shortpath_dijkstra(g);dijkstra最短路径问题programdijkstra;constinp=input.txt;oup=
12、output.txt;maxn=100;varga:dist:array1.maxn,1.maxnofinteger;array1.maxnofinteger;s:n,k:array1.maxnof0.1;integer;fp:text;procedureinit;vari,j:integer;beginassign(fp,inp);reset(fp);readln(fp,n,k);fori:=1tondoforj:=1tondoread(fp,gai,j);close(fp);end;proceduremain;vari,j,w,m:integer;beginfillchar(s,sizeof(s),0);fori:=1tondodisti:=maxint;distk:=0;fori:=1ton-1dobeginm:=maxint;forj:=1tondoif(sj=0)and(distj0)and(distw+gaw,jdistj)thendistj:=distw+gaw,j;end;end;procedurepri
