用C语言实现Dijkstra算法及测试用例

这个很早就写了，先把源代码发上来了，其他内容择日补充。

一、最短路径算法

例子：

二、源代码

/******************************
 * date:2011-3-31
 * filename:dijkstra_main.c
 * by:Jelline
 * ****************************/

#include <stdio.h>

#define MAX_WEIGHT 0X7FFFFFFF


int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[]);

void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr);

int main()
{
    //char vertex[] = {'a', '1', '2', '3', '4', '5', '6', 'b'};
    const char *vertexStr[8] = {"a", "v1", "v2", "v3", "v4", "v5", "v6", "b"};
    int adjMatrix[8][8] = {
        {MAX_WEIGHT, 2, 8, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
        {2, MAX_WEIGHT, 6, MAX_WEIGHT, 1, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT},
        {8, 6, MAX_WEIGHT, 7, 4, 2, 2, MAX_WEIGHT},
        {1, 7, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, MAX_WEIGHT},
        {MAX_WEIGHT, 1, 4, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 9},
        {MAX_WEIGHT, 2, MAX_WEIGHT, MAX_WEIGHT, 3, MAX_WEIGHT, 4, 6},
        {MAX_WEIGHT, MAX_WEIGHT, 2, 9, MAX_WEIGHT, 4, MAX_WEIGHT, 2},
        {MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 9, 6, 2, MAX_WEIGHT}
    };
    /*
    int adjMatrix[8][8] = {
      //{0, 1, 2, 3, 4, 5, 6, 7}
        {0, 2, 8, 1, 0, 0, 0, 0},
        {2, 0, 6, 0, 1, 0, 0, 0},
        {8, 6, 0, 7, 4, 2, 2, 0},
        {1, 7, 0, 0, 0, 0, 9, 0},
        {0, 1, 4, 0, 0, 3, 0, 9},
        {0, 2, 0, 0, 3, 0, 4, 6},
        {0, 0, 2, 9, 0, 4, 0, 2},
        {0, 0, 0, 0, 9, 6, 2, 0}
    };
    */

    /*
    int prev[8];
    int shortestPath = dijkstra(8, adjMatrix, 0, 7, prev);
    printf("the sum of shortest weight is %d\n", shortestPath);
    */
    printShortestPath(8, adjMatrix, 0, 7, vertexStr);

    return 0;
}


/******************************************************
 *Fuction:
 *      求图最短路径长度，并存储迹
 * Input:
 *      n--顶点个数
 *      adjMatrix[n][n]--图的邻接矩阵
 *      startV--源点
 *      endV--结束点
 *      prev[i]记录从源到顶点的最短路径上i的前一个顶点
 *Out:
 *      输出最短路径长度
 * ******************************************************/

int dijkstra(int n, int adjMatrix[][n], int startV, int endV, int prev[n])
{
    int dist[n]; //dist[i]表示从源到顶点i的最短特殊路径长度
    int mask[n]; //mask[i]标记顶点i是否加入集合 -1表示已加入集合
    int shortestPath = 0;
    int minWeight = MAX_WEIGHT;
    int minID;
    int i;
    int j;
    int tmp = 0;

    for (i=0; i<n; i++)
    {
        mask[i] = 0; //初始化集合为空集，即没有元素加入
        dist[i] = adjMatrix[startV][i]; //初始化dist[j]
        prev[i] = -1;
        prev[i] = (adjMatrix[startV][i] != MAX_WEIGHT) ? startV : -1;
    }


    //prev[0] = startV;
    // dist[startV] = -1; //起点标记为-1 不被更新
    mask[startV] = -1; //标记源点已加入

   for (i=1; i<n; i++)  //最多再加入n-1个顶点
   {
       minWeight = MAX_WEIGHT;
       //寻找下一个待加入的顶点
       for (j=0; j<n; j++)
       {
           if (mask[j]!=-1 && dist[j]<minWeight)
           {
               minWeight = dist[j];
               minID = j;
           }
       }

       mask[minID] = -1; //加入顶点

       if (minID == endV) //最后一个节点已加入
       {
           return dist[endV];
       }

       //更新dist[i]
       for (j=0; j<n; j++)
       {
           if (minWeight==MAX_WEIGHT || adjMatrix[minID][j]==MAX_WEIGHT)
               continue;
           tmp = minWeight + adjMatrix[minID][j];
           if(j!=startV && tmp<dist[j]) //起点无须更新
           {
               dist[j] = tmp;
               prev[j] = minID;
           }
       }

   }

}

//print path
void printShortestPath(int n, int adjMatrix[][n], int startV, int endV, const char **vertexStr)
{
    int prev[n];
    int shortestPath = dijkstra(n, adjMatrix, startV, endV, prev);
    printf("the shortest path is: %d=  ", shortestPath);
   int tmp = endV;
   do
   {
       printf("%s <--- ", vertexStr[tmp]);
       tmp = prev[tmp];
   }while(tmp != startV);
   printf("%s\n", vertexStr[startV]);

}

三、测试结果

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