網絡最短路徑Dijkstra算法解析

網絡最短路徑Dijkstra算法解析

最近在學習算法，看到有人寫過的這樣一個算法，我決定摘抄過來作為我的學習筆記：

/*
* File: shortest.c
* Description: 網絡中兩點最短路徑 Dijkstra 算法
*              Shortest Path Dijkstra Algorithm
* Created: 2001/11/25
* Author: Justin Hou [mailto:[email protected]]
*/

#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]);
    }
}