詳解Dijkstra算法原理及其C++實現

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <stack>

using namespace std;
using Matrix = vector<vector<uint>>;                // 連接矩陣（使用嵌套的vector表示）
using SNodes = vector<tuple<uint, uint, uint>>;     // 已計算出最短路徑的頂點集合S（類似一個動態數組）
using UNodes = list<tuple<uint, uint, uint>>;       // 未進行遍歷的頂點集合U（使用list主要是方便元素刪除操作）
using ENode = tuple<uint, uint, uint>;              // 每個節點包含（頂點編號，當前頂點到起始點最短距離，最短路徑中當前頂點的上一個頂點）信息


/***
 * 從未遍歷的U頂點集合中找到下一個離起始頂點距離最短的頂點
 * @param unvisitedNodes 未遍歷的U頂點集合
 * 每個元素是（頂點編號，當前頂點到起始點最短距離，最短路徑中當前頂點的上一個頂點）的tuple
 * @return 下一個離起始頂點距離最短的頂點
 */
ENode searchNearest(const UNodes &unvisitedNodes) {
    uint minDistance = UINT_MAX;
    ENode nearest;
    for (const auto &node: unvisitedNodes) {
        if (get<1>(node) <= minDistance) {
            minDistance = get<1>(node);
            nearest = node;
        }
    }
    return nearest;
}


/***
 * 迪克斯特拉算法的實現
 * @param graph 連接矩陣（使用嵌套的vector表示）
 * @param startNodeIndex 起始點編碼（從0開始）
 * @return 返回一個vector，每個元素是到起始頂點的距離排列的包含（頂點編號，當前頂點到起始點最短距離，最短路徑中當前頂點的上一個頂點）的tuple
 */
SNodes dijkstra(const Matrix &graph, uint startNodeIndex) {
    const uint numOfNodes = graph.size();   // 圖中頂點的個數
    // S是已計算出最短路徑的頂點的集合（頂點編號，當前頂點到起始點最短距離，最短路徑中當前頂點的上一個頂點）
    SNodes visitedNodes;
    // U是未計算出最短路徑的頂點的集合（其中的key為頂點編號，value為到起始頂點最短距離和最短路徑中上一個節點編號組成的pair）
    UNodes unvisitedNodes;

    // 對S和U集合進行初始化，起始頂點的距離為0，其他頂點的距離為無窮大
    // 最短路徑中當前頂點的上一個頂點初始化為起始頂點，後面會逐步進行修正
    for (auto i = 0; i < numOfNodes; ++i) {
        if (i == startNodeIndex) visitedNodes.emplace_back(i, 0, startNodeIndex);
        else unvisitedNodes.emplace_back(i, graph[startNodeIndex][i], startNodeIndex);
    }

    while (!unvisitedNodes.empty()) {
        // 從U中找到距離起始頂點距離最短的頂點，加入S，同時從U中刪除
        auto nextNode = searchNearest(unvisitedNodes);
        unvisitedNodes.erase(find(unvisitedNodes.begin(), unvisitedNodes.end(), nextNode));
        visitedNodes.emplace_back(nextNode);
        // 更新U集合中各個頂點的最短距離以及最短路徑中的上一個頂點
        for (auto &node: unvisitedNodes) {
            // 更新的判斷依據就是起始頂點到當前頂點（nextNode）距離加上當前頂點到U集合中頂點的距離小於原來起始頂點到U集合中頂點的距離
            // 更新最短距離的時候同時需要更新最短路徑中的上一個頂點為nextNode
            if (graph[get<0>(nextNode)][get<0>(node)] != UINT_MAX &&
                graph[get<0>(nextNode)][get<0>(node)] + get<1>(nextNode) < get<1>(node)) {
                get<1>(node) = graph[get<0>(nextNode)][get<0>(node)] + get<1>(nextNode);
                get<2>(node) = get<0>(nextNode);
            }
        }
    }

    return visitedNodes;
}


/***
 * 對使用迪克斯特拉算法求解的最短路徑進行打印輸出
 * @param paths vector表示的最短路徑集合
 * 每個元素是到起始頂點的距離排列的包含（頂點編號，當前頂點到起始點最短距離，最短路徑中當前頂點的上一個頂點）的tuple
 */
void print(const SNodes &paths) {
    stack<int> tracks;  //從尾部出發，使用stack將每個頂點的最短路徑中的前一個頂點入棧，然後出棧的順序就是最短路徑順序
    // 第一個元素是起始點，從第二個元素進行打印輸出
    for (auto it = ++paths.begin(); it != paths.end(); ++it) {
        // 打印頭部信息
        printf("%c -> %c:\t Length: %d\t Paths: %c",
               char(get<0>(paths[0]) + 65),
               char(get<0>(*it) + 65),
               get<1>(*it),
               char(get<0>(paths[0]) + 65));
        auto pointer = *it;
        // 如果當前指針pointer指向的節點有中途節點（判斷的條件是最短路徑中的前一個節點不是起始點）
        while (get<2>(pointer) != get<0>(paths[0])) {
            tracks.push(get<0>(pointer));
            // Lambda表達式，使用find_if函數把當前頂點的前一個頂點從paths中找出來繼續進行循環直到前一個節點就是起始點
            auto condition = [pointer](tuple<uint, uint, uint> x) { return get<0>(x) == get<2>(pointer); };
            pointer = *find_if(paths.begin(), paths.end(), condition);
        }
        tracks.push(get<0>(pointer));

        // 以出棧的順序進行打印輸出
        while (!tracks.empty()) {
            printf(" -> %c", char(tracks.top() + 65));
            tracks.pop();
        }
        printf("\n");
    }
}

int main() {
    Matrix graph = {
            {0,        12,       UINT_MAX, UINT_MAX, UINT_MAX, 16, 14},
            {12,       0,        10,       UINT_MAX, UINT_MAX, 7, UINT_MAX},
            {UINT_MAX, 10,       0, 3,               5,        6, UINT_MAX},
            {UINT_MAX, UINT_MAX, 3, 0,               4, UINT_MAX, UINT_MAX},
            {UINT_MAX, UINT_MAX, 5, 4,               0,        2,  8},
            {16,       7,        6,        UINT_MAX, 2,        9,  9},
            {14,       UINT_MAX, UINT_MAX, UINT_MAX, 8,        9,  0}
    };  // 圖對應的連接矩陣
    auto results = dijkstra(graph, uint('D' - 65));          // 選取頂點C（大寫字母A的ASCII編碼是65）
    print(results);     // 打印輸出結果
    return 0;
}