网络最短路径Dijkstra算法解析

最近在学习算法，看到有人写过的这样一个算法，我决定摘抄过来作为我的学习笔记：

 

/*
* file: shortest.c
* description: 网络中两点最短路径 dijkstra 算法
*              shortest path dijkstra algorithm
* created: 2001/11/25
* author: justin hou [mailto:[e-mail]]
*/

#include 
#define true  1
#define false 0
#define i  9999                                /* 无穷大        */
#define n  20                                  /* 城市顶点的数目 */

int cost[n][n] = {
    {0,3,i,i,i,1,i,i,i,i,i,i,i,i,i,i,i,i,i,i},
    {3,0,5,i,i,i,6,i,i,i,i,i,i,i,i,i,i,i,i,i},
    {i,5,0,4,i,i,i,1,i,i,i,i,i,i,i,i,i,i,i,i},
    {i,i,4,0,2,i,i,i,6,i,i,i,i,i,i,i,i,i,i,i},
    {i,i,i,2,0,i,i,i,i,7,i,i,i,i,i,i,i,i,i,i},
    {1,i,i,i,i,0,1,i,i,i,2,i,i,i,i,i,i,i,i,i},
    {i,6,i,i,i,1,0,6,i,i,i,7,i,i,i,i,i,i,i,i},
    {i,i,1,i,i,i,6,0,2,i,i,i,3,i,i,i,i,i,i,i},
    {i,i,i,6,i,i,i,2,0,8,i,i,i,4,i,i,i,i,i,i},
    {i,i,i,i,7,i,i,i,8,0,i,i,i,i,5,i,i,i,i,i},
    {i,i,i,i,i,2,i,i,i,i,0,4,i,i,i,3,i,i,i,i},
    {i,i,i,i,i,i,7,i,i,i,4,0,3,i,i,i,4,i,i,i},
    {i,i,i,i,i,i,i,3,i,i,i,3,0,3,i,i,i,5,i,i},
    {i,i,i,i,i,i,i,i,4,i,i,i,3,0,7,i,i,i,2,i},
    {i,i,i,i,i,i,i,i,i,5,i,i,i,7,0,i,i,i,i,3},
    {i,i,i,i,i,i,i,i,i,i,3,i,i,i,i,0,5,i,i,i},
    {i,i,i,i,i,i,i,i,i,i,i,4,i,i,i,5,0,8,i,i},
    {i,i,i,i,i,i,i,i,i,i,i,i,5,i,i,i,8,0,6,i},
    {i,i,i,i,i,i,i,i,i,i,i,i,i,2,i,i,i,6,0,4},
    {i,i,i,i,i,i,i,i,i,i,i,i,i,i,3,i,i,i,4,0}
};
int dist[n];                                          /* 存储当前最短路径长度 */
int v0 = 'a' - 65;                                    /* 初始点是 a          */

void main()
{
    int final[n], i, v, w, min;

    /* 初始化最短路径长度数据，所有数据都不是最终数据 */
    for (v = 0; v < n; v++) {
    final[v] = false;
        dist[v] = cost[v0][v];
    }

    /* 首先选v0到v0的距离一定最短，最终数据 */
    final[v0] = true;

    /* 寻找另外 n-1 个结点 */
    for (i = 0; i < n-1; i++) {
        min = i;                                      /* 初始最短长度无穷大  */
        
        /* 寻找最短的边 */
        for (w = 0; w < n; w++) {
            if (!final[w] && dist[w] < min) {
                min = dist[w];
                v = w;
        }
        }
        final[v] = true;                              /* 加入新边          */

        for (w = 0; w < n; w++) {                      /* 更新 dist[] 数据  */
            if (!final[w] && dist[v] + cost[v][w] < dist[w]) {
                dist[w] = dist[v] + cost[v][w];
            }
        }
    }

    for (i = 0; i < n; i++) {                          /* 显示到监视器      */
        printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
    }
}

运行结果：