作者:cuihao0532
轉載請注明出處：http://www.cnblogs.com/cuish/archive/2013/06/09/3129106.html
适用于有向圖和無向圖，鄰接矩陣存儲方式
1 //graph:鄰接矩陣形式存儲的有向圖或無向圖 2 //nLength:點的個數 3 //nStart:起點在鄰接矩陣中的位置 4 //nEnd:終點在鄰接矩陣中的位置 5 //INFINITY: 表示沒有路徑的最大值 6 //傳回值：儲存最短路徑正确順序的int數組，數組中隻有一個起點時說明沒有路徑 7 //D[]數組儲存起點到各個點的最短路徑長度 8 //需要注意的是：由于在代碼有中min + graph[nEnd, w]這樣的操作，是以最大值的選取要注意
9
10
11 public static int[] dijkstra(int[,] graph, int nLength, int nStart, int nEnd, INT INFINITY ) 12 { 13 int t = nEnd; 14 int[] P = new int[nLength]; 15 int[] D = net int [nLength]; 16 int[] final = new int[nLength]; 17
18 for(int i = 0; i < nLength; ++ i) 19 { 20 D[i] = graph[nStart, i]; 21 P[i] = nStart; 22 final[i] = 0; 23
24 } //for
25
26 final[nStart] = 1; 27
28 for(int i = 1;i < nLength; ++ i) 29 { 30 int min = INFINITY; //最大值
31 for(int w = 0; w < nLength; ++ w) 32 { 33 if(final[w] == 0 && D[w] < min) 34 { 35 nEnd = w; 36 min = D[w]; 37 } 38 } //for
39
40 final[nEnd] = 1; 41
42 for(int w = 0; w < nLength; ++ w) 43 { 44 if(final[w] == 0 && (min + graph[nEnd, w] < D[w])) 45 { 46 D[w] = min + graph[nEnd, w]; 47 P[w] = nEnd; 48 }//if
49
50 } //for
51
52 } //for
53
54 string r = null; 55 if(D[t] < INFINITY) 56 { 57 r = t.ToString() + ","; //最短路徑上的第一個點為本身(後面要把這個順序逆置)
58 } 59
60 do
61 { 62 r += P[t].ToString() + ","; //找所有的路徑上的點;
63 t = P[t]; 64 }while(t != nStart); 65
66 char[] arr = r.ToCharArray(); 67 Array.Reverse(arr); //逆置
68
69 string strRet = new string(arr); //逆置後的string
70
71 string[] str = strRet.Split(new char[] {','}); //按逗号分割
72 int [] nArrResult = new int[str.Length - 1]; //第一個為空，減少一個
73
74 for(int count = 1; count < str.Length; ++ count) 75 { 76 nArrResult[count - 1] = int.Parse(str[count]); 77 } 78
79 return nArrResult; 80
81
82 }
轉載于:https://my.oschina.net/u/926461/blog/350876