Dijkstra算法原理及C++怎么實(shí)現(xiàn)

這篇文章主要介紹“Dijkstra算法原理及C++怎么實(shí)現(xiàn)”的相關(guān)知識(shí)，小編通過(guò)實(shí)際案例向大家展示操作過(guò)程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“Dijkstra算法原理及C++怎么實(shí)現(xiàn)”文章能幫助大家解決問(wèn)題。

什么是最短路徑問(wèn)題

如果從圖中某一頂點(diǎn)（稱為源點(diǎn)）到達(dá)另一頂點(diǎn)（稱為終點(diǎn)）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。

單源最短路徑問(wèn)題是指對(duì)于給定的圖G=(V,E)，求源點(diǎn)v₀到其它頂點(diǎn)v_t的最短路徑。

Dijkstra算法

Dijkstra算法用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。Dijkstra是一種按路徑長(zhǎng)度遞增的順序逐步產(chǎn)生最短路徑的方法，是一種貪婪算法。

Dijkstra算法的核心思想是首先求出長(zhǎng)度最短的一條最短路徑，再參照它求出長(zhǎng)度次短的一條最短路徑，依次類推，直到從源點(diǎn)v₀到其它各頂點(diǎn)的最短路徑全部求出為止。

具體來(lái)說(shuō)：圖中所有頂點(diǎn)分成兩組，第一組是已確定最短路徑的頂點(diǎn)，初始只包含一個(gè)源點(diǎn)，記為集合S；第二組是尚未確定最短路徑的頂點(diǎn)，記為集合U。

按最短路徑長(zhǎng)度遞增的順序逐個(gè)把U中的頂點(diǎn)加到S中去，同時(shí)動(dòng)態(tài)更新U集合中源點(diǎn)到各個(gè)頂點(diǎn)的最短距離，直至所有頂點(diǎn)都包括到S中。

實(shí)現(xiàn)思路

1.初始時(shí)，S集合只包含起點(diǎn)v₀；U集合包含除v₀外的其他頂點(diǎn)v_t，且U中頂點(diǎn)的距離為起點(diǎn)v₀到該頂點(diǎn)的距離。（U 中頂點(diǎn)v_t的距離為(v₀,v_t)的長(zhǎng)度，如果v₀和v_t不相鄰，則v_t的最短距離為∞）

2.從U中選出距離最短的頂點(diǎn)v_t′，并將頂點(diǎn)v_t′加入到S中；同時(shí)，從U中移除頂點(diǎn)v_t′。

3.更新U中各個(gè)頂點(diǎn)v_t到起點(diǎn)v₀的距離以及最短路徑中當(dāng)前頂點(diǎn)的前驅(qū)頂點(diǎn)。之所以更新U中頂點(diǎn)的距離以及前驅(qū)頂點(diǎn)是由于上一步中確定了v_t′是求出最短路徑的頂點(diǎn)，從而可以利用v_t′來(lái)更新U中其它頂點(diǎn)v_t的距離，因?yàn)榇嬖?v₀,v_t)的距離可能大于(v₀,v_t')+(v_t',v_t)距離的情況，從而也需要更新其前驅(qū)頂點(diǎn)

4.重復(fù)步驟(2)和(3)，直到遍歷完所有頂點(diǎn)

案例分析

代碼實(shí)現(xiàn)

使用了部分C++11特性，注釋豐富，讀起來(lái)應(yīng)該不會(huì)太困難！

#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>>;     // 已計(jì)算出最短路徑的頂點(diǎn)集合S（類似一個(gè)動(dòng)態(tài)數(shù)組）
using UNodes = list<tuple<uint, uint, uint>>;       // 未進(jìn)行遍歷的頂點(diǎn)集合U（使用list主要是方便元素刪除操作）
using ENode = tuple<uint, uint, uint>;              // 每個(gè)節(jié)點(diǎn)包含（頂點(diǎn)編號(hào)，當(dāng)前頂點(diǎn)到起始點(diǎn)最短距離，最短路徑中當(dāng)前頂點(diǎn)的上一個(gè)頂點(diǎn)）信息


/***
 * 從未遍歷的U頂點(diǎn)集合中找到下一個(gè)離起始頂點(diǎn)距離最短的頂點(diǎn)
 * @param unvisitedNodes 未遍歷的U頂點(diǎn)集合
 * 每個(gè)元素是（頂點(diǎn)編號(hào)，當(dāng)前頂點(diǎn)到起始點(diǎn)最短距離，最短路徑中當(dāng)前頂點(diǎn)的上一個(gè)頂點(diǎn)）的tuple
 * @return 下一個(gè)離起始頂點(diǎn)距離最短的頂點(diǎn)
 */
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;
}


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

    // 對(duì)S和U集合進(jìn)行初始化，起始頂點(diǎn)的距離為0，其他頂點(diǎn)的距離為無(wú)窮大
    // 最短路徑中當(dāng)前頂點(diǎn)的上一個(gè)頂點(diǎn)初始化為起始頂點(diǎn)，后面會(huì)逐步進(jìn)行修正
    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中找到距離起始頂點(diǎn)距離最短的頂點(diǎn)，加入S，同時(shí)從U中刪除
        auto nextNode = searchNearest(unvisitedNodes);
        unvisitedNodes.erase(find(unvisitedNodes.begin(), unvisitedNodes.end(), nextNode));
        visitedNodes.emplace_back(nextNode);
        // 更新U集合中各個(gè)頂點(diǎn)的最短距離以及最短路徑中的上一個(gè)頂點(diǎn)
        for (auto &node: unvisitedNodes) {
            // 更新的判斷依據(jù)就是起始頂點(diǎn)到當(dāng)前頂點(diǎn)（nextNode）距離加上當(dāng)前頂點(diǎn)到U集合中頂點(diǎn)的距離小于原來(lái)起始頂點(diǎn)到U集合中頂點(diǎn)的距離
            // 更新最短距離的時(shí)候同時(shí)需要更新最短路徑中的上一個(gè)頂點(diǎn)為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;
}


/***
 * 對(duì)使用迪克斯特拉算法求解的最短路徑進(jìn)行打印輸出
 * @param paths vector表示的最短路徑集合
 * 每個(gè)元素是到起始頂點(diǎn)的距離排列的包含（頂點(diǎn)編號(hào)，當(dāng)前頂點(diǎn)到起始點(diǎn)最短距離，最短路徑中當(dāng)前頂點(diǎn)的上一個(gè)頂點(diǎn)）的tuple
 */
void print(const SNodes &paths) {
    stack<int> tracks;  //從尾部出發(fā)，使用stack將每個(gè)頂點(diǎn)的最短路徑中的前一個(gè)頂點(diǎn)入棧，然后出棧的順序就是最短路徑順序
    // 第一個(gè)元素是起始點(diǎn)，從第二個(gè)元素進(jìn)行打印輸出
    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;
        // 如果當(dāng)前指針pointer指向的節(jié)點(diǎn)有中途節(jié)點(diǎn)（判斷的條件是最短路徑中的前一個(gè)節(jié)點(diǎn)不是起始點(diǎn)）
        while (get<2>(pointer) != get<0>(paths[0])) {
            tracks.push(get<0>(pointer));
            // Lambda表達(dá)式，使用find_if函數(shù)把當(dāng)前頂點(diǎn)的前一個(gè)頂點(diǎn)從paths中找出來(lái)繼續(xù)進(jìn)行循環(huán)直到前一個(gè)節(jié)點(diǎn)就是起始點(diǎn)
            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));

        // 以出棧的順序進(jìn)行打印輸出
        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}
    };  // 圖對(duì)應(yīng)的連接矩陣
    auto results = dijkstra(graph, uint('D' - 65));          // 選取頂點(diǎn)C（大寫(xiě)字母A的ASCII編碼是65）
    print(results);     // 打印輸出結(jié)果
    return 0;
}

運(yùn)行結(jié)果：

D -> C:     Length: 3     Paths: D -> C
D -> E:     Length: 4     Paths: D -> E
D -> F:     Length: 6     Paths: D -> E -> F
D -> G:     Length: 12     Paths: D -> E -> G
D -> B:     Length: 13     Paths: D -> C -> B
D -> A:     Length: 22     Paths: D -> E -> F -> A

關(guān)于“Dijkstra算法原理及C++怎么實(shí)現(xiàn)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。