網絡中兩點最短路徑 Dijkstra 算法

c++實現兩點最短路徑 Dijkstra 算法
更多 0
c++
最短路徑
算法

網絡中兩點最短路徑 Dijkstra 算法
/*

File: shortest.c
Description: 網絡中兩點最短路徑 Dijkstra 算法
Shortest Path Dijkstra Algorithm
*/

include <stdio.h>
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]);
}

}</pre>