dijkstra.cpp

// DIJKSTRA on weighted GRAPH 
// O(n+mlog(m)) time complexity
// vertices start from 1 onwards
// can't work in case of negative edges
#include <bits/stdc++.h>
using namespace std;
const int INF=1e7;

class Graph{
    int vertices;
    vector<pair<int,int>>*adj;
    int *parent;
    bool *visited;
public:
    Graph(int v);
    ~Graph(){
        delete [] adj;
        delete []parent;
        delete [] visited;
        cout<<"\n";
    }
    void addedge(int a,int b,int w);
    void visit_false();
    void dijkstra(int source);
    void printpath(int dest);
};
Graph::Graph(int v){
    vertices=v;
    adj=new vector<pair<int,int>>[v];
    parent=new int[v];
    visited=new bool[v];
}
void Graph::addedge(int a,int b,int w){
    adj[a].push_back({b,w});
    adj[b].push_back({a,w});
}
void Graph::visit_false(){
    for(int i=0;i<vertices;i++){
        visited[i]=false;
    }
}

void Graph::dijkstra(int s){
    priority_queue<pair<int,int>>pq;
    int distance[vertices];
    for(int i=0;i<vertices;i++){
        distance[i]= INF;
    }
    distance[s]=0;
    parent[s]=-1;
    pq.push({0,s});
    while(!pq.empty()){
        int a=pq.top().second; pq.pop();
        if(visited[a]){
            continue;
        }
        visited[a]=true;
        for(auto u: adj[a]){
            int b=u.first,w=u.second;
            if(distance[a]+w < distance[b]){
                parent[b]=a;
                distance[b]=distance[a]+w;
                pq.push({-distance[b],b});
            }
        }
    }
    cout<<"\n\ndistance of nodes from source:"<<s+1<<"\n";
    for(int i=0;i<vertices;i++){
        cout<<i+1<<" : "<<distance[i]<<"unit\n";
    }
}
void Graph::printpath(int dest){
    if(parent[dest]==-1){
        return;
    }
    printpath(parent[dest]);
    cout<<parent[dest]+1<<" ";
}

int main() {
    int vertices,edges;
    cout<<"Enter no of vertices & edges\n";
    cin>>vertices>>edges;
    Graph g(vertices);
    cout<<"Enter pair of adjacent vertices with weight\n";
    for(int i=0;i<edges;i++){
        int a,b,w;
        cin>>a>>b>>w;
        g.addedge(a-1,b-1,w);
    }
    int source,dest;
    cout<<"enter source from which u find min distance\n";
    cin>>source;
        source--;
        g.visit_false();
        g.dijkstra(source);
    cout<<"enter destination\n";
    cin>>dest;
        cout<<"shortest path from "<<source+1<<" to "<<dest<<"\n";
        dest--;
        g.printpath(dest);
        cout<<dest+1<<"\n";
	return 0;
}


// input
/*
5 7
1 2 7
1 3 3
3 2 1
3 4 2
4 5 4
2 5 6
2 4 2
1
5
*/

// output
/*
Enter no of vertices & edges
Enter pair of adjacent vertices with weight
enter source from which u find min distance


distance of nodes from source:1
1 : 0unit
2 : 4unit
3 : 3unit
4 : 5unit
5 : 9unit
enter destination
shortest path from 1 to 5
1 3 4 5

*/