用C語言實現Dijkstra算法及測試用例

源代碼發上。

一、最短路徑算法

例子：

二、源代碼

1. /******************************
   
2. * date:2011-3-31
3. * filename:dijkstra_main.c
4. * by:Jelline
5. * ****************************/
7. #include <stdio.h>
9. #define MAX_WEIGHT 0X7FFFFFFF
12. int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[]);
14. void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr);
16. int main()
17. {
18. //char vertex[] = {'a', '1', '2', '3', '4', '5', '6', 'b'};
19. const char *vertexStr[8] = {"a", "v1", "v2", "v3", "v4", "v5", "v6", "b"};
20. int adjMatrix[8][8] = {
21. {MAX_WEIGHT, 2, 8, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
22. {2, MAX_WEIGHT, 6, MAX_WEIGHT, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
23. {8, 6, MAX_WEIGHT, 7, 4, 2, 2, MAX_WEIGHT},
24. {1, 7, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, MAX_WEIGHT},
25. {MAX_WEIGHT, 1, 4, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 9},
26. {MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 4, 6},
27. {MAX_WEIGHT, MAX_WEIGHT, 2, 9, MAX_WEIGHT, 4, MAX_WEIGHT, 2},
28. {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, 6, 2, MAX_WEIGHT}
29. };
30. /*
    
31. int adjMatrix[8][8] = {
32. //{0, 1, 2, 3, 4, 5, 6, 7}
33. {0, 2, 8, 1, 0, 0, 0, 0},
34. {2, 0, 6, 0, 1, 0, 0, 0},
35. {8, 6, 0, 7, 4, 2, 2, 0},
36. {1, 7, 0, 0, 0, 0, 9, 0},
37. {0, 1, 4, 0, 0, 3, 0, 9},
38. {0, 2, 0, 0, 3, 0, 4, 6},
39. {0, 0, 2, 9, 0, 4, 0, 2},
40. {0, 0, 0, 0, 9, 6, 2, 0}
41. };
42. */
44. /*
    
45. int prev[8];
46. int shortestPath = dijkstra(8, adjMatrix, 0, 7, prev);
47. printf("the sum of shortest weight is %d\n", shortestPath);
48. */
49. printShortestPath(8, adjMatrix, 0, 7, vertexStr);
51. return 0;
52. }
55. /******************************************************
    
56. *Fuction:
57. * 求圖最短路徑長度，並存儲跡
58. * Input:
59. * n--頂點個數
60. * adjMatrix[n][n]--圖的鄰接矩陣
61. * startV--源點
62. * endV--結束點
63. * prev[i]記錄從源到頂點的最短路徑上i的前一個頂點
64. *Out:
65. * 輸出最短路徑長度
66. * ******************************************************/
68. int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[n])
69. {
70. int dist[n]; //dist[i]表示從源到頂點i的最短特殊路徑長度
71. int mask[n]; //mask[i]標記頂點i是否加入集合 -1表示已加入集合
72. int shortestPath = 0;
73. int minWeight = MAX_WEIGHT;
74. int minID;
75. int i;
76. int j;
77. int tmp = 0;
79. for (i=0; i<n; i++)
80. {
81. mask[i] = 0; //初始化集合為空集，即沒有元素加入
82. dist[i] = adjMatrix[startV][i]; //初始化dist[j]
83. prev[i] = -1;
84. prev[i] = (adjMatrix[startV][i] != MAX_WEIGHT) ? startV : -1;
85. }
88. //prev[0] = startV;
89. // dist[startV] = -1; //起點標記為-1 不被更新
90. mask[startV] = -1; //標記源點已加入
92. for (i=1; i<n; i++) //最多再加入n-1個頂點
93. {
94. minWeight = MAX_WEIGHT;
95. //尋找下一個待加入的頂點
96. for (j=0; j<n; j++)
97. {
98. if (mask[j]!=-1 && dist[j]<minWeight)
99. {
100. minWeight = dist[j];
101. minID = j;
102. }
103. }
105. mask[minID] = -1; //加入頂點
107. if (minID == endV) //最後一個節點已加入
108. {
109. return dist[endV];
110. }
112. //更新dist[i]
113. for (j=0; j<n; j++)
114. {
115. if (minWeight==MAX_WEIGHT || adjMatrix[minID][j]==MAX_WEIGHT)
116. continue;
117. tmp = minWeight + adjMatrix[minID][j];
118. if(j!=startV && tmp<dist[j]) //起點無須更新
119. {
120. dist[j] = tmp;
121. prev[j] = minID;
122. }
123. }
125. }
127. }
129. //print path
130. void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr)
131. {
132. int prev[n];
133. int shortestPath = dijkstra(n, adjMatrix, startV, endV, prev);
134. printf("the shortest path is: %d= ", shortestPath);
135. int tmp = endV;
136. do
137. {
138. printf("%s <--- ", vertexStr[tmp]);
139. tmp = prev[tmp];
140. }while(tmp != startV);
141. printf("%s\n", vertexStr[startV]);
143. }

三、測試結果

the shortest path is: 11= b <--- v6 <--- v2 <--- v4 <--- v1 <--- a