用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.        }
104.        
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.    }
126.    
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