Djikestra Shortest Path Algorithm : LEDA performance

I have written this program which tests LEDA library performance for shortest path algorithm performance. This library is pretty good. Much easier to use than boost libraries.


/*
* =====================================================================================
*
*       Filename:  dikkstra.cpp
*
*    Description:  Dijksjtra algorithm for calculating shortest path.
*
*        Version:  1.0
*        Created:  Tuesday 06 December 2011 04:45:57  IST
*       Revision:  none
*       Compiler:  gcc
*
*         Author:  Dilawar Singh (Graduate Student, EE IITB), dilawar@ee.iitb.ac.in
*      Institute:  IIT Bombay
*
* =====================================================================================
*/

#include    <LEDA/graph/graph.h>
#include    <LEDA/graph/node_pq.h>

using namespace leda;
using namespace std;

/* fun : DIJKESTRA
* Args : a const graph, starting node
*        array of edges.
*        array of nodes
*/

void DIJKESTRA
( const graph &G, node s,
const edge_array<double>& cost,
node_array<double>& dist)
{
node_pq<double> PQ(G); /* priority queue */
node v; edge e;

forall_nodes(v,G)
{
if (v == s)
dist[v] = 0;
else
dist[v] = MAXDOUBLE;
PQ.insert(v, dist[v]);
}

while( !PQ.empty())
{
node u = PQ.del_min();
forall_out_edges(e,u)
{
v = target(e);
double c = dist[u] + cost[e];
if(c < dist[v])
{
PQ.decrease_p(v,c); dist[v] = c;
}
}
}
}

int main()
{
int n = 1; // = read_int("number of nodes = ");
int m = 1; // = read_int("number of edges = ");
graph G;
edge e;
cout << "\nTime, Nodes, Edges\n";
int i;
for(i = 0; i < 50000; i++)
{
random_graph(G,n,m);
edge_array<double> cost(G);
node_array<double> dist(G);
forall_edges(e,G)
cost[e] = ((double) rand_int(0,100));

float T = used_time();
DIJKESTRA(G, G.first_node(), cost, dist);
cout<<used_time(T)<<","<<n<<","<<m<<"\n";
n = (i+10)*(i+10) - 9*i;
m = rand_int(1,3)*n;
}

return 0;
}
&nbsp;

Give appropriate path and libraries to compiler.

Advertisements

About Dilawar

Graduate Student at National Center for Biological Sciences, Bangalore.
This entry was posted in Graph Theory, Mathematics, Programming and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s