用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

相关内容