Dijkstra

Dijkstra.cpp

/**
*   author:     roccoshi
*   created:    2021-03-08 21:34:14
*   description: 
    dijkstra + priority_queue
    test_cases: 
    node1 node2 distance
    [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
*/
#pragma GCC diagnostic ignored "-Wsign-conversion"
#pragma GCC diagnostic ignored "-Wsign-compare"
#include<bits/stdc++.h>
using namespace std;

class dijkstra {
private:
    // nodes[v] = [{w1, d1}, {w2, d2}, {w3, d3}...]
    vector<vector<pair<int, int>>> nodes;
    // the number of nodes
    int n;
public:
    // init
    // nodes: edges[i][0]->edges[i][1]
    // distance: edges[i][2]
    dijkstra (int n, vector<vector<int>>& edges) {
        this->n = n;
        nodes.resize(n);
        // undirected graph, node starts from 1, so count with: node = node - 1
        for (auto& i : edges) {
            int node1 = i[0] - 1, node2 = i[1] - 1, d = i[2];
            nodes[node1].emplace_back(node2, d);
            nodes[node2].emplace_back(node1, d);
        }
    }

    // v0: source node
    vector<int> solve (int v0) {
        // pq.top() -> {d, v}: current minimum distance from v0
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<int> dis(n, INT_MAX);
        dis[v0] = 0;
        pq.emplace(0, v0);
        vector<bool> vis(n, false);
        while (!pq.empty()) {
            pair<int, int> x = pq.top(); pq.pop();
            int d = x.first, w = x.second;

            if (vis[w]) continue;
            vis[w] = true;
            // dis[w] = d;
            for (auto& i : nodes[w]) {
                if (d + i.second < dis[i.first]) {
                    dis[i.first] = d + i.second;
                    pq.emplace(dis[i.first], i.first);
                }
            }
        }
        return dis;
    }
};


int main() {
    /*code*/
    int n = 5;
    vector<vector<int>> edges{{1,2,3},{1,3,3},{2,3,1},{1,4,2},{5,2,2},{3,5,1},{5,4,10}};
    dijkstra test(n, edges);
    for (int v = 0; v < n; ++v) {
        vector<int> ans = test.solve(v);
        cout << "select " << v << " as the beginning node" << endl;
        for (int i = 0; i < ans.size(); ++i) {
            cout << i << " " << ans[i] << endl;
        }
    }
    
    return 0;
}