Dijkstra_Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

vector<int> dijkstra(int N,
                     vector<pair<int,int>> adj[],
                     int source)
{
    vector<int> dist(N, INT_MAX);

    priority_queue<
        pair<int,int>,
        vector<pair<int,int>>,
        greater<pair<int,int>>
    > pq;

    dist[source] = 0;
    pq.push({0, source});

    while(!pq.empty())
    {
        int currentDist = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        // Skip outdated entries
        if(currentDist > dist[currentNode])
            continue;

        for(auto edge : adj[currentNode])
        {
            int nextNode = edge.first;
            int weight = edge.second;

            if(dist[currentNode] + weight < dist[nextNode])
            {
                dist[nextNode] =
                    dist[currentNode] + weight;

                pq.push({dist[nextNode], nextNode});
            }
        }
    }

    return dist;
}

int main()
{
    int N, M;
    cin >> N >> M;

    vector<pair<int,int>> adj[N];

    for(int i = 0; i < M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // undirected graph
    }

    int source;
    cin >> source;

    vector<int> dist = dijkstra(N, adj, source);

    cout << "\nShortest Distances:\n";

    for(int i = 0; i < N; i++)
    {
        cout << "Node " << i
             << " : " << dist[i]
             << endl;
    }

    return 0;
}