Dijstra算法的C++实现

图论中Dijstra算法算是比较经典的算法，它解决的是一个有权图中，指定起始点到其他顶点的最短距离，采用的是BFS的思想，网上有很多版本，我这里参考youtube上的教程：https://www.youtube.com/watch?v=9wV1VxlfBlI
，基于C++语言以及priority queue实现了一下，有兴趣的同学可以研究下：

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <limits.h>
#include <set>

using  namespace std;
struct Dist {
    char id;    // 顶点
    int dist;   // 目标点到该顶点的距离
    bool operator < (const Dist& a) const {
        return this->dist > a.dist;
    }
};

class Solution {
public:
    void getShortestDist(map<char, vector<Dist>>& graph, map<char, int>& dists, char start) {
        priority_queue<Dist> myQ;       // 采用优先队列处理图中的顶点，并且重载<运算符，构建最小堆
        set<char> mySet;                // 采用set容器记录已处理的顶点
        Dist firstOne = {start, 0};
        myQ.push(firstOne);

        while (!myQ.empty()) {
            Dist tmpD = myQ.top();
            myQ.pop();  // 一定要在这里马上pop掉，否则在后面pop的话可能不是tmpD的顶点！！！！
            if (mySet.find(tmpD.id) == mySet.end()) {
                for (auto& d : graph[tmpD.id]) {
                    if (mySet.find(d.id) != mySet.end()) {
                        continue;
                    } else {
                        Dist nextD;
                        nextD.id = d.id;
                        nextD.dist = d.dist + tmpD.dist;
                        //cout << "nextD.id = " << nextD.id << ", dist = " << nextD.dist << endl;
                        myQ.push(nextD);
                    }
                }
                mySet.insert(tmpD.id);
                dists[tmpD.id] = tmpD.dist;
            } else {
                continue;
            }
        }
    }
};

int main() {
    map<char, vector<Dist>> myGraph;     // 存放图的描述信息
    map<char, int> shortestDists;       // 存放目标点到各点之间的最短距离

    // 创建一个测试图
    myGraph = {
            {'A', {{'B', 5}, {'C', 1}}},
            {'B', {{'A', 5}, {'C', 2}, {'D', 1}}},
            {'C', {{'A', 1}, {'B', 2}, {'D', 4}, {'E', 8}}},
            {'D', {{'B', 1}, {'C', 4}, {'E', 3}, {'F', 6}}},
            {'E', {{'C', 8}, {'D', 3}}},
            {'F', {{'D', 6}}}
    };

    Solution solver;
    solver.getShortestDist(myGraph, shortestDists, 'A');
    // 打印结果
    for (auto it : shortestDists) {
        cout << "To " << it.first << ": shortest dist = " << it.second << endl;
    }

    return 0;
}