Dijkstra算法求最短路径(C#版).doc

1、Dijkstra算法求最短路径 (C# 版) 日期： 2009-06-25来源：作者：字体： 大 中 小 行如下图的路径,(V0 是中心 ): 经过该算法后转化为下图 usingSystem; usingSystem.Collections; usingSystem.Text; namespaceGreedy class Marx privateintdistance; privateint row; privateArrayListways = new ArrayList(); public Marx(intn,paramsintd) this.row= n; distance= new i

2、ntrow* row; for (int i = 0; i row * row;i+) this.distancei=di; for (int i = 0; i this.row;i+)/ 有 row 个点，则从中心到各点的路有row- 1 条 ArrayListw = new ArrayList(); int j = 0; w.Add(j); ways.Add(w); /- public void Find_way() ArrayListS = new ArrayList(1); ArrayListSr =new ArrayList(1); int Indexof_distance=newi

3、ntthis.row; for(inti=0;i row;i+) Indexof_distancei=i; S.Add( Indexof_distance0); for (int i = 0; i 0) / 假定中心点的编号是0 的贪吃法求路径 for (inti =0; i row;i+) Di=this.distancei; int min_num= (int)Sr0;/ 距中心点的最小距离点编号 foreach(ints in Sr) if (Ds Dmin_num)min_num= s; / 以上可以排序优化 S.Add(min_num); Sr.Remove(min_num); /-

4、把最新包含进来的点也加到路径中- (ArrayList)waysmin_num).Add(min_num); /- foreach(intelementin Sr) int position= element* (this.row)+ min_num; bool exchange= false;/ 有交换标志 if (Delement Dmin_num+ this.distanceposition) Delement= Delement; else Delement= this.distanceposition+ Dmin_num; exchange= true; / 修改距离矩阵 this.

5、distanceelement=Delement; position= element* this.row; this.distanceposition= Delement; / 修改路径 - if (exchange=true) (ArrayList)wayselement).Clear(); foreach (intpointin (ArrayList)waysmin_num) (ArrayList)wayselement).Add(point); -Count; public voidDisplay() /- 中心到各点的最短路径- Console.WriteLine(中心到各点的最短路

6、径如下:nn); int sum_d_index= 0; foreach(ArrayList motherin ways) foreach(int childin mother) Console.Write(V0 -, child+1); Console.WriteLine(路径长0,distancesum_d_index+); classMainEnterPoint static voidMain(string args) int r;/ 列数 Console.Write( 请输入点个数（含配送中心点）:); Int32.TryParse(Console.ReadLine(),out r);

7、 Console.WriteLine(各点分别为 : n); for (inti = 0; i r; i+) Console.Write(V0, i); Console.Write(假定第一个点是配送中心); Console.WriteLine(nn输入各点之间的距离(无通径的用个大整数表示)n); int a= new intr* r; int da; for (inti = 0; i r; i+) for(int j = i + 1;j r;j+) Console.Write(V0到 V1 的距离是 :,i,j); Int32.TryParse(Console.ReadLine(),out da); ai *r+ j= da; Console.WriteLine(); /- 完善距离矩阵 (距离矩阵其实可以是个上三角矩阵， /- 但为了处理方便，还是将其完整成一个对称阵)- for (inti = 0; i r; i+) for(int j = 0; j r; j+) if (i = j) ai *r+ j= 0; aj *r+ i= ai *r+ j; Marx m=newMarx(r,a); Console.WriteLine(); m.Find_way(); m.Display(); / 该程序不但能够算出从中心到各点的最短路径距离,而且把路径也保存了下来