Shortest path by Dijkstra

Algorithm Name: Dijkstra
Algorithm Category:  Graph search algorithm

Source Code:
////////////////////////////////////////////// // Bismillahir Rahmanir Rahim // // Author : Shohan Ahmed Sijan // // Country : Bangladesh // // University : East West University // ///////////////////////////////////////// #pragma warning(disable:4786) #include <cstdio> #include <queue> #include <iostream> #include <utility> using namespace std; #define Max 999999999 #define Size 1009 int node,edge,cost[Size],path[Size],start,dest,sc,i,j,c,source,destination; bool visit[Size]; pair <int,int>p,pp; queue< pair<int,int> >q[Size]; void Dijkstra(int s,int d) { cost[s]=0; priority_queue < pair<int,int> >pq; pq.push(pair<int,int>(-cost[s],s)); while(pq.empty()==false) { p=pq.top(); pq.pop(); sc=p.second; if(sc==d)break; visit[sc]=true; while(q[sc].empty()==false) { pp=q[sc].front(); q[sc].pop(); i=pp.first; if(visit[i]==false && cost[sc]+pp.second<cost[i]) { cost[i]=cost[sc]+pp.second; path[i]=sc; pq.push(pair<int,int>(-cost[i],i)); } } } } void getpath(int d) { if(path[d]!=-1) { getpath(path[d]); printf(" %d",d); } } int main() { scanf("%d %d %d %d",&node,&edge,&source,&destination); for(i=0;i<=node;i++) { cost[i]=Max; visit[i]=false; path[i]=-1; while(q[i].empty()==false) q[i].pop(); } for(i=0;i<edge;i++) { scanf("%d %d %d",&start,&dest,&c); q[start].push(pair<int,int>(dest,c)); q[dest].push(pair<int,int>(start,c)); } Dijkstra(source,destination); if(cost[destination]!=Max) { printf("Minimum cost is %d\n",cost[destination]); printf("Path is:%d",source); getpath(destination); printf("\n"); } else printf("Unreachable\n"); return 0; }

Input:
5 5 7 1 5 1 2 3 2 3 2 1 5 7 5 4 2 3 4 5 1 4 4 3 5 4

Output:
Minimum cost is 6 Path is:1 4 5