dijkstra Alogrithm implement in c++ (with details)

//dijkstra

#include<bits/stdc++.h>
using namespace std;
#define mx 100002
#define INF 10000 //boro kono man
vector<int>g[mx],cost[mx]; //g[] হচ্ছে গ্রুফ cost[] weight
struct node
{
    int u,w;
    node(int a,int b){u=a; w=b;}
    bool operator < ( const node& p ) const {      return w > p.w;   } //priority_queue এর condition
};
int d[mx],par[mx];
int src,dest;
int dijkstra(int n)
{
    memset(d,INF,sizeof(d)); //sob noder cost infinity
    memset(par,-1,sizeof(par)); //parent so -1
    priority_queue<node>q; //q toiri kora holo
    q.push(node(0,1)); //prothm node ta push kora hoece
    d[0]=0; //source er cost 0 kora hoece
    while(!q.empty())
    {
        node top=q.top(); q.pop();
        int u=top.u;

        if(u==dest) return d[dest]; //jodi destination e powcia jae tahole return korbo
        int v;
        for(int i=0;i<(int)g[u].size();i++)
        {
            v=g[u][i];
            if(d[u]+cost[u][i]<d[v]) //condition of update
            {
                d[v]=d[u]+cost[u][i]; //update
                par[v]=u; //parent toiri korlam

                q.push(node(v,d[v]));
            }
        }

    }
    return -1;
}
int main(){
    int n,e; //gruph input
    cin>>n>>e; //vertex and edge number
    for(int i=0;i<e;i++)
    {
        int u,v; //2 ta node
        int w; //tader cost
        cin>>u>>v>>w;
        g[u].push_back(v);
        g[v].push_back(u); //jehetu undirected gruph so u-v and v-u
        cost[u].push_back(w);
        cost[v].push_back(w);

    }
    cout<<"Enter source and destination: ";
    cin>>src>>dest;
    int ret=dijkstra(src);
    cout<<"Path length: "<<ret<<endl; // sortest path length src to dest
    if(ret==-1) puts("No path!");
    else
    {
        int u=dest;
        vector<int>out;
        while(u!=-1)
        {
            out.push_back(u);

            u=par[u];

        }
        reverse(out.begin(),out.end());
        for(int i=0;i<(int)out.size();i++)
            cout<<out[i]<<" ";
        puts("");

    }
}



====================================================
Simple input :
4 4
0 1 5
0 3 8
1 3 6
3 2 10
simple output:
18
0 3 2

SHARE

Amit Ghosh

• 
• 
• 
• 
•