dijkstra

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<set>
#define INF 1000000000
typedef std::vector<int> distances;
typedef std::pair<int, int> p;
typedef std::vector<p> graph;
graph *G;   //here will be stored the graph
distances dist; //here will be stored the distances for every node


//-----------------dijkstra----------------------------//
void dijkstra(int source, int n)
{
    dist.assign(n, INF);
    dist[source] = 0;
    std::set<p> Q;
    Q.insert({0, source});
    while (!Q.empty())
    {
        auto top = Q.begin();
        int u = top->second;
        Q.erase(top);
        for (auto& e : G[u])
        {
            int v = e.first;
            int w = e.second;
            if (dist[v] > dist[u] + w)
            {
                if (Q.find({ dist[v],v }) != Q.end())
                    Q.erase(Q.find({ dist[v],v }));
                dist[v] = dist[u] + w;
                Q.insert({ dist[v],v });
            }
        }
    }
}
void main_dijkstra()
{
    int n, m, u, v, w, source;
    std::cout << "Give the no of nodes and the no of edges:";
    std::cin >> n >> m;
    G = new graph[n + 1];
    std::cout << "Give the edges(their extremes and the weigh):" << std::endl;
    for (int i = 0; i < m; i++)
    {
        std::cin >> u >> v >> w;
        G[u].push_back({ v,w });
        G[v].push_back({ u,w });
    }
    std::cout << "Give the source:";
    std::cin >> source;


    dijkstra(source, n);
    for (int i = 0; i < n; i++)
    {
        std::cout << dist[i] << " " << std::endl;
    }
}

//---------------optimised dijkstra--------------------//

void dijkstra_priority_queue(int source, int N)
{
    //create a priority queue to store the pairs of nodes
    std::priority_queue<p, std::vector<p>, std::greater<p>> Q;
    dist.assign(N, INF);
    dist[source] = 0;
    Q.push({ 0,source });
    while (!Q.empty())
    {
        int a = Q.top().second;
        Q.pop();
        for (auto &e : G[a])
        {
            int b = e.first;
            int c = e.second;

            if (dist[b]>dist[a] + c)
            {
                dist[b] =dist[a]+ c;
                Q.push({ dist[b],b });
            }
        }
    }
}

void main_dijkstra_priority_queue()
{
    int n, m, u, v, w, source;
    std::cout << "Give the no of nodes and the no of edges:";
    std::cin >> n >> m;
    G = new graph[n + 1];
    std::cout << "Give the edges(their extremes and the weigh):"<<std::endl;
    for (int i = 0; i < m; i++)
    {
        std::cin >> u >> v >> w;
        G[u].push_back({ v,w });
        G[v].push_back({ u,w });
    }
    std::cout << "Give the source:";
    std::cin >> source;


    dijkstra_priority_queue(source, n);
    for (int i = 0; i < n; i++)
    {
        std::cout << dist[i] << " " << std::endl;
    }
}
//----------------optimised dijkstra--------------------//

int main()
{
    std::cout << "----------------------------------dijkstra----------------------" << std::endl;
    main_dijkstra();

    std::cout << "---------------------------optimised dijkstra----------------------" << std::endl;
    main_dijkstra_priority_queue();
    return 0;
}