參考書籍：數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社

基本概念

Dijkstra算法：Dijkstra提出了一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法。
Dijkstra算法解決的對象：單源點最短路徑問題。

算法實現(xiàn)思路

• 圖中所有邊存儲在鄰接表中，所有的頂點存儲在一個結(jié)構(gòu)體組中，通過其下標對頂點進行操作

結(jié)構(gòu)體聲明

1. 邊結(jié)構(gòu)體的聲明

typedef struct ArcNode{
    int adjvexNum; //該弧所指向的頂點在圖的定點結(jié)構(gòu)體組中的下角標
    struct ArcNode *nextarc;
    int weight;
}ArcNode;

• adjvexNum 為這條邊的尾頂點的數(shù)組下標。
• nextarc 為鄰接表的下一條與頂點鄰接的邊。
• weight 為邊的權(quán)值。

2. 頂點結(jié)構(gòu)體的聲明

typedef struct VexNode{
    ArcNode *firstarc;
    int known;
    int dist;
    int path;
    int data;
}VexNode,AdjList[MAX_VERTEX_NUM];

• firstarc 指向其鄰接表
• known 表示該節(jié)點的最短路徑是否已經(jīng)明確。
• dist 表示源點到該頂點的最短路徑的長度（權(quán)值之和）
• path 表示Dijkstra算法中某個頂點的在最短路徑中的前序頂點，在算法過程中可能會發(fā)生改變。

3. 圖結(jié)構(gòu)體聲明

typedef struct {
    AdjList vertice;
    int vexnum,arcnum;  // 圖當前頂點數(shù)和邊數(shù)
    GraphKind kind; //圖的種類類型
}MGraph;

• vertice 用來存儲一個圖中頂點信息的數(shù)組

圖的創(chuàng)建

void addEdge(int a,int b,int weight,MGraph &G){
    int vex1,vex2;
    for(int i = 0; i < G.vexnum; i++){ //通過用戶輸入的數(shù)據(jù)匹配頂點對應(yīng)的下標
        if(a == G.vertice[i].data){
            vex1 = i;
        }
        if(b == G.vertice[i].data){
            vex2 = i;
        }
    }
    ArcNode *arcNode = (ArcNode*)malloc(sizeof(ArcNode)); //初始化所有邊
    arcNode->nextarc = NULL;
    arcNode->adjvexNum = vex2;
    arcNode->weight = weight;

    if(G.vertice[vex1].firstarc == NULL){    //將邊加入到鄰接表
        G.vertice[vex1].firstarc = arcNode;
    }
    else{
        ArcNode *t = NULL;
        ArcNode *pre = NULL;
        for(t = G.vertice[vex1].firstarc;t != NULL;t = t->nextarc){
            pre = t;
        }
        pre->nextarc = arcNode;
    }
}

void CreateGraph(MGraph &G){
    //scanf("%d %d",&G.vexnum,&G.arcnum);
    G.vexnum = 7;
    G.arcnum = 12;
    for(int i = 0; i < G.vexnum; i++) {  //初始化所有頂點
        G.vertice[i].firstarc = NULL;
        G.vertice[i].known = 0;
        G.vertice[i].dist = INT_MAX;
        G.vertice[i].path = -1;
    }
    G.vertice[0].data = 1;
    G.vertice[1].data = 2;
    G.vertice[2].data = 3;
    G.vertice[3].data = 4;
    G.vertice[4].data = 5;
    G.vertice[5].data = 6;
    G.vertice[6].data = 7;
//for(int k = 0; k < G.arcnum; k++){
// int vex1,vex2,weight;  //輸入一條邊的起點和終點以及這條邊的權(quán)值
//  scanf("%d %d",&vex1,&vex2);
//}
    int a[12]={
            1,1,2,2,3,3,4,4,4,4,5,7
    };
    int b[12]={
            2,4,4,5,1,6,3,5,6,7,7,6
    };
    int weight[12]={
            2,1,3,10,4,5,2,2,8,4,6,1
    };
    for(int i = 0; i < G.arcnum; i++)
    addEdge(a[i],b[i],weight[i],G);
}

• 初始化所有頂點的known值為0
• 初始化所有頂點的dist值為INT_MAX，為了滿足Dijkstra算法尋找最短路徑的操作，所以初值要設(shè)定為最大值。
• 所有頂點的前序節(jié)點path都默認為 -1，方便在所有節(jié)點都得到前置節(jié)點時通過-1找到初始節(jié)點并停止尋找path。

Dijkstra 算法

void Dijkstra(MGraph G)
{
    G.vertice[0].known = 1; // 初始化源節(jié)點
    G.vertice[0].dist = 0;
    for (ArcNode *t = G.vertice[0].firstarc; t; t = t->nextarc) {
        G.vertice[t->adjvexNum].dist = t->weight;
        G.vertice[t->adjvexNum].path = 0;
    }
    int k; // 權(quán)值最小路徑尾頂點下標
    for(int i = 1; i < G.vexnum; i++){
        int min = INT_MAX;
        for (int j = 0; j < G.vexnum; j++)
        {
            if (G.vertice[j].known == 0 && G.vertice[j].dist < min)
            {
                min = G.vertice[j].dist;
                k = j;
            }
        }
        G.vertice[k].known = 1;  // 標記"頂點k"為已經(jīng)獲取到最短路徑
        for (ArcNode *t = G.vertice[k].firstarc; t; t = t->nextarc) {
            if (!G.vertice[t->adjvexNum].known) {
                if(G.vertice[k].dist + t->weight < G.vertice[t->adjvexNum].dist) {
                    G.vertice[t->adjvexNum].dist = G.vertice[k].dist + t->weight;
                    G.vertice[t->adjvexNum].path = k;
                }
            }
        }
    }
    int target = 6;  // 用戶輸入的終點
    int dataset[100];  // 用于整理path數(shù)據(jù)正向輸出路徑
    int dataNum = 0;
    for(int i = 0; i < G.vexnum; i++){
        if(G.vertice[i].data == target){
            for(int k = i; k != -1; k = G.vertice[k].path){ // 正序輸出最小路徑
                dataset[dataNum] = G.vertice[k].data;
                dataNum++;
            }
            for(int l = dataNum-1;l > 0; l--){
                printf("%d,",dataset[l]);
            }
            printf("%d",dataset[0]);
        }
    }
}

1. 源點數(shù)據(jù)初始化

G.vertice[0].known = 1; // 初始化源節(jié)點
G.vertice[0].dist = 0;

2. 為源點鄰接的頂點設(shè)置dist值和path值

for (ArcNode *t = G.vertice[0].firstarc; t; t = t->nextarc) {
        G.vertice[t->adjvexNum].dist = t->weight;
        G.vertice[t->adjvexNum].path = 0;
    }

3. 開始循環(huán)判斷所有除源點以外其他頂點的dist值和path值

• 循環(huán)進行下述兩步操作

int min = INT_MAX;
        for (int j = 0; j < G.vexnum; j++)
        {
            if (G.vertice[j].known == 0 && G.vertice[j].dist < min)
            {
                min = G.vertice[j].dist;
                k = j;
            }
        }

• 找到與該頂點 j 相鄰最近的點 k（對應(yīng)的邊權(quán)值最?。?/li>

G.vertice[k].known = 1;  // 標記"頂點k"為已經(jīng)獲取到最短路徑
        for (ArcNode *t = G.vertice[k].firstarc; t; t = t->nextarc) {
            if (!G.vertice[t->adjvexNum].known) {
                if(G.vertice[k].dist + t->weight < G.vertice[t->adjvexNum].dist) {
                    G.vertice[t->adjvexNum].dist = G.vertice[k].dist + t->weight;
                    G.vertice[t->adjvexNum].path = k;
                }
            }
        }

• 與所有與點k相鄰的點比較其dist值
• k點的dist值與k點到鄰點邊的權(quán)值之和與其相鄰的點的dist值比較，若前者小，則更新路徑值dist和前序頂點path。

原理

• 若該節(jié)點沒有被賦值，則dist值為正無窮，判斷結(jié)果一定失敗。
• 若該節(jié)點有過值通過k點的最短路徑長度和與其相鄰的權(quán)值足以與之前的dist值對應(yīng)的情況進行比較哪個是更短的路徑，對每個頂點入度的情況都遍歷檢查了一遍，達到效率較優(yōu)的情況下檢查全圖得到源點到目標頂點最短路徑的目的。