算法簡易過程：

•  迪杰斯特拉算法（樸素） O(n^2)
  G={V,E}   V：點(diǎn)集合   E:邊集合
  初始化時(shí) 令 S={某源點(diǎn)ear}, T=V-S= {其余頂點(diǎn)}，T中頂點(diǎn)對應(yīng)的距離（ear， Vi）值
            若存在，d(ear,Vi)為弧上的權(quán)值， dist【i】
            若不存在，d(ear,Vi)為 無窮大， dist【i】
   循環(huán) n - 1次（n個(gè)點(diǎn)）：
    1、從T中選取一個(gè)與S中頂點(diǎn) 有關(guān)聯(lián)邊 且 權(quán)值最小 的頂點(diǎn) pos，加入到 S中
        (這里使用 flag數(shù)組來確定 是否屬于 S集合，true為屬于）
        (等于是 每次 選取 T點(diǎn)集中 dist最小的頂點(diǎn) 作為 pos 加入 S，既 flag置為 true)
    2、對其余T中頂點(diǎn)Vi的距離值進(jìn)行修改：若加進(jìn) pos 作中間頂點(diǎn)，從ear -> pos -> Vi 的距離值縮短，則 ??更新dist
        (等于是 找出所有 pos -> Vi 邊（有邊連接的）， 再加上原來源ear -> pos 權(quán)重，對比dist數(shù)組，如果權(quán)重更小則更新 => 更新dist最短路徑長度，更新prev數(shù)組 更新前驅(qū)頂點(diǎn)為pos)

求單源有向圖最短路徑

使用鄰接表法來存儲頂點(diǎn)和邊，錄入有向圖。

（當(dāng)然也可以無向圖，不過錄入時(shí)要錄入兩次，比如 a b 3? ? ? ? b a 3）

?代碼如下：

//
// Created by Giperx on 2022/11/27.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define INFINE 99999 // 定義最大
// 鄰接表
struct ArcNode // 邊信息
{
    int adjvex;//有向邊的 目標(biāo)頂點(diǎn) 下標(biāo)（從1開始）
    int weight;//邊的權(quán)值
    struct ArcNode *next; //鄰接表，指向下一個(gè)鄰接邊信息
};

struct VertexNode // 頂點(diǎn)
{
    int vertex;//頂點(diǎn)下標(biāo)（1 ~）
    ArcNode *firstedge;// 有向邊信息節(jié)點(diǎn)指針（源為vertex）
};

struct AdjList // 圖
{
    vector<VertexNode> adjlist;//頂點(diǎn)數(shù)組
    int vexnum;  //頂點(diǎn)數(shù)　
    int arcnum;  //邊數(shù)
};

// 圖的初始化
void createGraph(AdjList& G){
    cout << "輸入頂點(diǎn)數(shù) 邊數(shù)：" << endl;
    cin >> G.vexnum >> G.arcnum;
    // 初始化G的頂點(diǎn)數(shù)組
    for(int i = 0; i <= G.vexnum; i ++){ // 下標(biāo)從1開始，所以初始化vexnum + 1個(gè)頂點(diǎn)（0無作用）
        VertexNode* tmp = new VertexNode;
        tmp->vertex = i, tmp->firstedge = nullptr;
        G.adjlist.emplace_back(*tmp);
    }
    //邊信息
    // n1:源頂點(diǎn)     n2:目標(biāo)頂點(diǎn)   we:權(quán)重（距離）
    int n1, n2, we;
    cout << "輸入邊信息：（a b we）：" << endl; // a -> b  weight: we
    for(int i = 0; i < G.arcnum; i ++){
        cin >> n1 >> n2 >> we;
        // 初始化一個(gè)邊節(jié)點(diǎn)，目標(biāo)頂點(diǎn)為n2
        ArcNode* tmp = new ArcNode;
        tmp->adjvex = n2, tmp->weight = we;
        // 頭插法 將邊信息節(jié)點(diǎn)插入
        // 節(jié)約時(shí)間（尾插要一直遍歷到尾部插入）
        tmp->next = G.adjlist[n1].firstedge;
        G.adjlist[n1].firstedge = tmp;
    }
}

// 獲取兩頂點(diǎn)之間權(quán)重weight（距離）
int getWeight(AdjList& G, int n1, int n2){
    if(n1 == n2) return 0;

    ArcNode* tmp = G.adjlist[n1].firstedge;
    while(tmp){
        if(tmp->adjvex == n2) return tmp->weight;
        tmp = tmp->next;
    }
    // 兩點(diǎn)之間沒有邊，返回INFINE
    return INFINE;
}

// 迪杰斯特拉算法（樸素）
//G={V,E}   V：點(diǎn)集合   E:邊集合
//初始化時(shí) 令 S={某源點(diǎn)ear}, T=V-S= {其余頂點(diǎn)}，T中頂點(diǎn)對應(yīng)的距離（ear， Vi）值
//          若存在，d(ear,Vi)為弧上的權(quán)值， dist【i】
//          若不存在，d(ear,Vi)為 無窮大， dist【i】
// 循環(huán) n - 1次（n個(gè)點(diǎn)）：
//  從T中選取一個(gè)與S中頂點(diǎn) 有關(guān)聯(lián)邊 且 權(quán)值最小 的頂點(diǎn) pos，加入到 S中
//      (這里使用 flag數(shù)組來確定 是否屬于 S集合，true為屬于）
//      (等于是 每次 選取 T點(diǎn)集中 dist最小的頂點(diǎn) 作為 pos 加入 S，既 flag置為 true)
//  對其余T中頂點(diǎn)Vi的距離值進(jìn)行修改：若加進(jìn) pos 作中間頂點(diǎn)，從ear -> pos -> Vi 的距離值縮短，則 更新dist
//      (等于是 找出所有 pos -> Vi 邊（有邊連接的）， 再加上原來源ear -> pos 權(quán)重，
//      對比dist數(shù)組，如果權(quán)重更小則更新 => 更新dist最短路徑長度，更新prev數(shù)組 更新前驅(qū)頂點(diǎn)為pos)
void Dijkstra(AdjList& G, int ear, vector<int>& prev, vector<int>& dist){
    // 初始化
    // flag數(shù)組記錄 某點(diǎn)是否納入已找到點(diǎn)集合
    // prev數(shù)組記錄 前驅(qū)頂點(diǎn)下標(biāo)
    // dist數(shù)組記錄 從源頂點(diǎn)ear 到 i頂點(diǎn)的最短路徑
    vector<bool> flag (G.adjlist.size() + 1, false);
    for(int i = 1; i <= G.vexnum; i ++) dist[i] = getWeight(G, ear, i), prev[i] = ear;
    flag[ear] = true, prev[ear] = 0;
    // 開始
    for(int i = 2; i <= G.vexnum; i ++){
        int pos = 1; // 未納入的距離最小的頂點(diǎn)
        int weiMin = INFINE;
        for(int j = 1; j <= G.vexnum; j ++){
            if(!flag[j] && dist[j] < weiMin){
                weiMin = dist[j], pos = j;
            }
        }

        flag[pos] = true;
        for(int j = 1; j <= G.vexnum; j ++){
            if(!flag[j]){ // 未納入點(diǎn)集中，找到pos到這些點(diǎn)的距離，與dist數(shù)組比較是否更新
                int tmpWei = getWeight(G, pos, j);
                if(tmpWei != INFINE) tmpWei = tmpWei + weiMin; // 兩點(diǎn)距離應(yīng)該為ear -> pos -> j
                if(tmpWei < dist[j]) {
                    dist[j] = tmpWei; // 距離更小則更新dist
                    prev[j] = pos; // 前頂點(diǎn)更新為pos
                }
            }
        }
    }

}

// 找路徑
void pathDist(vector<int>& prev, vector<int>& dist, int ear){
    // prev數(shù)組中為1有2種情況（djikstra初始化過程的時(shí)候全賦值為1，后續(xù)一直未改變）：
    // 1：從ear到 頂點(diǎn) 只有 ear -> 頂點(diǎn) 這一條路最短
    // 2：無法從ear到達(dá)的頂點(diǎn)
    for(int i = 1; i <= prev.size() - 1; i ++){
        stack<int> trace;
        if(ear == i) continue;
        cout << ear << " 到 " << i ;
        // 無連通
        if(dist[i] == INFINE) {
            cout << "無連通" << endl;
            continue;
        }
        cout << "最短距離：" << dist[i] << "  最短路徑：";
        int tmp = i;
        while(tmp){ //  源頂點(diǎn)prev是0
            trace.push(tmp);
            tmp = prev[tmp];
        }
        // 開始出棧, 棧頂一定是ear源頂點(diǎn)
        cout << trace.top();
        trace.pop();
        while(!trace.empty()){
            cout << " -> " << trace.top();
            trace.pop();
        }
        cout << endl;
    }
}
int main(){
    AdjList G;
    createGraph(G);
    // prev數(shù)組記錄 前驅(qū)頂點(diǎn)下標(biāo)
    vector<int> prev (G.vexnum + 1, 0);
    // dist數(shù)組記錄 從源頂點(diǎn)ear 到 i頂點(diǎn)的最短路徑
    vector<int> dist (G.vexnum + 1, INFINE);
    // 從源點(diǎn)ear 出發(fā)，到達(dá)其余所有點(diǎn)的最短路徑
    cout << "輸入源頂點(diǎn)ear：";
    int ear;
    cin >> ear;
    Dijkstra(G, ear,prev, dist);
    pathDist(prev, dist, ear);
//    for(int &x:prev) cout << x << ' ';
//    for(int &x:dist) cout << x << ' ';
    return 0;
}

測試如下：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-465239.html

到了這里，關(guān)于dijkstra迪杰斯特拉算法（鄰接表法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！