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

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

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。