DIJESTRA

#include<bits/stdc++.h>
using namespace std;

int adj[100][100];
int d[100];
int v;

struct edge
{
    int node;
    int distance;

    bool operator < (const edge& p) const
    {
        return distance>p.distance;
    }
};

void dijkstra(int source)
{
    priority_queue<edge> p;  //a priority queue is an abstract data type which is like a regular queue or stack data structure,
    //but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before
    //an element with low priority. If two elements have the same priority, they are served according to their order in the queue

    for(int i=1;i<=v;i++)
    {
        d[i]=1000000;
    }

    d[source]=0;

    edge temp;

    temp.distance=0;
    temp.node=source;

    p.push(temp);

    while(!p.empty())
    {
        temp=p.top();
        p.pop();

        for(int i=1;i<=v;i++)
        {
            if(adj[temp.node][i]!=0)
            {
                edge t;

                t.node=i;
                t.distance=d[temp.node]+adj[temp.node][i];

                if(d[i]>t.distance)
                {
                    d[i]=t.distance;
                    p.push(t);
                }
            }
        }
    }
}

int main()
{
    int a,b,w,count=1;

    cout<<"Enter number of Vartex : ";
    cin>>v;

    while(1)
    {
        cout<<"Edge "<<count<<" : ";

        cin>>a>>b>>w;

        if(a>v || b>v)
        {
            cout<<"Wrong input"<<endl;
        }
        else if(a==0 && b==0)
        {
            break;
        }
        else
        {
            adj[a][b]=w;
            count++;
        }
    }

    dijkstra(1);

    for(int i=1;i<=v;i++)
    {
        cout<<d[i]<<" ";
    }
}