迪杰斯特拉算法求最短路徑

    #include "iostream"


#include "memory.h"  
using namespace std;  

const int num = 9; //節點個數  
#define Infinity 65535  

void dijk(int *distance, int *p, int graphic[num][num], int source) {  
    //distance記錄從source到其他節點的最短距離  
    bool isvisted[num]; //記錄一個節點是否被訪問過  
    memset(p, 0, sizeof(p));  //記錄在最短路徑中，當前節點的父節點  
    memset(isvisted, false, sizeof(isvisted));  
    //初始化  
    for (int i = 0; i < num; i++){  
        distance[i] = graphic[source][i];  
    }  
    isvisted[source] = true;  
    distance[source] = 0;  

    for (int i = 0; i < num; i++){  
        int min = Infinity;  
        int index;  
        //找出到source距離最短的未被訪問過的節點  
        for (int j = 0; j < num; j++){  
            if (!isvisted[j] && distance[j] < min){  
                index = j;  
                min = distance[j];  
            }  
        }  
        isvisted[index] = true;  
        //修正其他節點到source的最短距離  
        for (int j = 0; j < num; j++){  
            if (!isvisted[j] && (min + graphic[index][j]) < distance[j]){  
                distance[j] = min + graphic[index][j];  
                p[j] = index;  
            }  
        }  
    }  
}  

int main(){  
    int graphic[num][num];  
    for (int i = 0; i < num; i++)  
    for (int j = 0; j < num; j++){  
        if (i == j)  
            graphic[i][j] = 0;  
        else  
        graphic[i][j] = Infinity;  
    }  
    graphic[0][1] = 1;  
    graphic[0][2] = 5;  
    graphic[1][0] = 1;  
    graphic[1][2] = 3;  
    graphic[1][3] = 7;  
    graphic[1][4] = 5;  
    graphic[2][0] = 5;  
    graphic[2][1] = 3;  
    graphic[2][4] = 1;  
    graphic[2][5] = 7;  
    graphic[3][1] = 7;  
    graphic[3][4] = 2;  
    graphic[3][6] = 3;  
    graphic[4][1] = 5;  
    graphic[4][2] = 1;  
    graphic[4][3] = 2;  
    graphic[4][5] = 3;  
    graphic[4][6] = 6;  
    graphic[4][7] = 9;  
    graphic[5][2] = 7;  
    graphic[5][4] = 3;  
    graphic[5][7] = 5;  
    graphic[6][3] = 3;  
    graphic[6][4] = 6;  
    graphic[6][7] = 2;  
    graphic[6][8] = 7;  
    graphic[7][4] = 9;  
    graphic[7][5] = 5;  
    graphic[7][6] = 2;  
    graphic[7][8] = 4;  
    graphic[8][6] = 7;  
    graphic[8][7] = 4;  
    int distance[num];  
    int p[num];  
    dijk(distance, p, graphic, 1);  
    for (int i = 0; i < num; i++) {  
        cout << distance[i] << endl;  
    }  
    return 0;  
}  </pre>