﻿ Tips And Tutorial - Presented by Oneous!

Single-Source Shortest Path problem - Dijkstra algorithm
Last Update: 6 March, 2008

Problem: Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.

My Code:

``````//// C++ code - Single-Source Shortest Path problem - Dijkstra Algorith

#include<cstdio>
#include<cmath>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define INF  2147483647
#define CLEAR(A,N)  (memset(A,0,(N)*sizeof(A)))

////////////////// Dijkstra's algorithm   //////////////////////
typedef struct
{
int n,cost;
}node;

bool operator < (node x, node y)
{
return x.cost > y.cost;
}

int used;
vector<node> v;

int Dijkstra(int s, int d, int n)
{
int i;
priority_queue<node> q;
node t,cur;

t.n=s;
t.cost=0;
q.push(t);
CLEAR(used,n+1);

while(!q.empty())
{
t=q.top();
q.pop();

if(t.n==d)
return t.cost;
if(used[t.n]==1)
continue;
used[t.n]=1;

for(i=0; i<v[t.n].size(); i++)
{
cur=v[t.n][i];
if(used[cur.n]==0)
{
cur.cost=cur.cost+t.cost;
q.push(cur);
}
}
}
return -1;
}

void reset(int n)
{
int i;
for(i=0;i<=n;i++)
v[i].clear();
}

int main()
{
//freopen("in.txt","rt",stdin)
//freopen("out.txt","wt",stdout)
int test,n,m,S,T,i,a,b,c,Cas=1,res;

scanf("%d",&test);
while(test--)
{
scanf("%d %d %d %d",&n,&m,&S,&T);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&a,&b,&c);
node t;
t.cost=c;
t.n=b;
v[a].push_back(t);
t.n=a;
v[b].push_back(t);
}

res=Dijkstra(S,T,n);
if(res!=-1)
printf("Case #%d: %d\n",Cas++,res);
else
printf("Case #%d: unreachable\n",Cas++);
reset(n);
}

// End of main function.......
return 0;
}

/***  Programmed by:
#####################
##   ORONNO        ##
## CSEDU 12th Batch.##
######################
Note: This program is not totally
useless. Because, at least, this
might be used as a bad example!!!!
**********************************/``````