Dijkstra's Algorithm

Introduction:

Given a graph and a source vertex in graph, find shortest paths from source to all vertices in the given graph.
Let's take a real life example:

Like Prim’s minimum spanning tree algo, we generate aSPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has minimum distance from source.

Implementation using recursion:-


#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
vector<pair<int,int>>arr[10];
pair<int,int>p;

int source;
bool sptset[10];
void initialize(int distance[],int v){

    for(int i=0;i<=v;i++){

        sptset[i]=false;
        distance[i]= INT_MAX;
    }
}
int min_distance(int v,int distance[]){

    int min=INT_MAX,index;

    for(int i=0;i<=v;i++){

        if(distance[i]<min && (!sptset[i])){

                min=distance[i];
                index=i;
        }

    }
    return index;
}
void print(int distance[],int v){

    for(int i=0;i<=v;i++){


        cout<<"The distance of : "<<i<<" from source node is "<<distance[i]<<endl;
    }
}

void Dijkstra(int v,int count,int distance[]){

    if(count==v-1){


        print(distance,v-1);
        exit(0);

    }
    int min=min_distance(v,distance);
    sptset[min]=true;
    for(int j=0;j<arr[min].size();j++){

        if(!sptset[arr[min][j].first] && distance[min]!=INT_MAX  && ((distance[min]+arr[min]                     [j].second)<distance[arr[min][j].first])){

            distance[arr[min][j].first]=distance[min]+arr[min][j].second;

        }
    }
    count++;
    Dijkstra(v,count,distance);
}

main(){

    int v,e,x,y,weight;
    cin>>v>>e;

    for(int i=0;i<e;i++){

        cin>>x>>y;
        cin>>weight;

        p.first=y;///MOST IMPORTANT PART OF code to avoid segfault;
        p.second=weight;
        arr[x].push_back(p);
    }
    cout<<"Enter source : ";
    cin>>source;
    int count=0;
    int distance[v+1];
    initialize(distance,v);
    distance[source]=0;
    Dijkstra(v,count,distance);

}