Dijkstra

/**
 * Dijkstra's algorithm. 
 * In essence, Dijkstra's algorithm maintains two sets: one set of nodes whose
 * distance from source is NOT finalized, one set of nodes whose distance
 * from source IS finalized. 
 * In implementation, we keep track of the two sets explicitly or implicitly. 
 * 
 * https://leetcode.com/problems/path-with-maximum-probability/solutions/732293/dijkstras-algorithm-implementation-c/
 * 
 */

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

// Helper functions
vector<vector<pair<int, int>>> buildGraph(int n, vector<vector<int>>& edges, vector<int>& weights) {
    vector<vector<pair<int, int>>> graph(n);
    for (int i = 0; i < edges.size(); i++) {
        vector<int> edge = edges[i];
        graph[edge[0]].push_back({edge[1], weights[i]});
        graph[edge[1]].push_back({edge[0], weights[i]});
    }
    return graph;
}

void printSolution(vector<int>& dist) {
    printf("Vertex \tDistance from Source\n");
    for (int i = 0; i < dist.size(); i++)
        printf("  %d \t\t\t %d\n", i, dist[i]);

    cout << "\n\n" << endl;
}

class Solution {
   public:

    vector<int> getShortestPathsUsingDijkstraUsingPrioirityQueue(vector<vector<pair<int, int>>>& graph, int src) {
        
        int n = graph.size();
        
        vector<int> dist(n, INT_MAX);



        auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2) {
            // pair<distance, node> => this pair is different from pair in the graph.
            // This pair is an entry in the priority_queue
            return p1.first > p2.first; 
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> unfinalized(comp);


        
        dist[src] = 0;
        unfinalized.push({0, src});



        while (!unfinalized.empty()) {
            int u = unfinalized.top().second;
            unfinalized.pop();

            for (int i = 0; i < graph[u].size(); i++) {
                int v = graph[u][i].first, weight = graph[u][i].second;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    unfinalized.push({dist[v], v});
                }
            }
        }

        return dist;
    }
};

int main() {
    Solution sol;
    int n = 9;

    vector<vector<int>> edges({{0, 1},
                               {0, 7},
                               {1, 2},
                               {1, 7},
                               {2, 3},
                               {2, 8},
                               {2, 5},
                               {3, 4},
                               {3, 5},
                               {4, 5},
                               {5, 6},
                               {6, 7},
                               {6, 8},
                               {7, 8}});
    vector<int> weights({4, 8, 8, 11, 7, 2, 4, 9, 14, 10, 2, 1, 6, 7});

    vector<vector<pair<int, int>>> graph = buildGraph(n, edges, weights);

    // adjacency list, with C++ priority_queue
    vector<int> dist = sol.getShortestPathsUsingDijkstraUsingPrioirityQueue(graph, 0);

    printSolution(dist);

}