implementing dijkstra algorithm using fibonacci heap and linked list...........
can anybody help me with the coding for this problem..................
i hav implemented using array now i hav to implement it using fibonacci heap and linked list.............

Recommended Answers

All 3 Replies

So you did it in C++ AND VB.net ?? Very interesting. Please show some code to prove you've made an effort.

Niek

hey,one advice dont mind,instead of writing the title hai everybody or hai,,,,writet the title fibonocci series,,then more replies are there if ur title is appropriate

ya i hav done it in c++

#include<iostream>
#include<fstream>
#include"dij_class.h"
#include<time.h>

using namespace std;

void dijkstra::read()
{
 cout<<"Enter the number of vertices\n";
 cin>>num_of_vertices;
 while(num_of_vertices<=0)
{
  cout<<"\nthis is meaningless,enter the number carefully\n";
cin>>num_of_vertices;
}
 cout<<"Enter the adjacent matrix:\n";
 for(int i=1;i<=num_of_vertices;i++)
 {
  cout<<"\nenter the weights for the row\n"<<i<<"\n";
  for(int j=1;j<=num_of_vertices;j++)
  {
   cin>>graph[i][j];
   while(graph[i][j]<0)
   {
    cout<<"\nu should enter the positive valued weights only\nenter the value again\n";
    cin>>graph[i][j];
   }
  }
 }
cout<<"\nenter the source vertex\n";
cin>>source;

}

void dijkstra::initialize()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
  mark[i]=0;
  pathestimate[i]=999;
  predecessor[i]=0;
 }
 pathestimate[source]=0;
}

void dijkstra::algorithm()
{

//calculating time
 int time1,time2;
 time1=time(NULL);
 cout<<"TIME:"<<time1<<endl;
 initialize();
 int count=0;
 int i;
 int u;
while(count<num_of_vertices)
 {
  u=minimum();
  set[++count]=u;
  mark[u]=1;
  for(i=1;i<=num_of_vertices;i++)
  {
   if(graph[u][i]>0)
   {
    if(mark[i]!=1)
    {
    if(pathestimate[i]>pathestimate[u]+graph[u][i])
    {
     pathestimate[i]=pathestimate[u]+graph[u][i];
     predecessor[i]=u;
    }
    }
   }
  }
 }
time2=time(NULL);
cout<<time2;
}

void dijkstra::printpath(int i)
{
cout<<endl;
if(i==source)
{
cout<<source;
}
else if(predecessor[i]==0)
cout<<"no path from "<<source<<" to "<<i;
else
{
printpath(predecessor[i]);
cout<<".."<<i;
}
}

void dijkstra::output()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
 printpath(i);
 if(pathestimate[i]!=999)
  cout<<"->("<<pathestimate[i]<<")\n";
 }
 cout<<endl;
}

int dijkstra::minimum()
{
 int min=999;
 int i,t;
 for(i=1;i<=num_of_vertices;i++)
 {
  if(mark[i]!=1)
  {
   if(min>=pathestimate[i])
   {
   min=pathestimate[i];
   t=i;
   }
  }
 }
 return t;
}



//main

#include<iostream>
#include"dij_class.h"


using namespace std;

void main()
{
 dijkstra s;
 s.read();
 s.algorithm();
 s.output();
}

//class

class dijkstra
{
private:
 int graph[50][50];
 int set[50],predecessor[50],mark[50],pathestimate[50];
 int source;
 int num_of_vertices;
public:
 int minimum();
 void read();
 void initialize();
 void printpath(int);
 void algorithm();
 void output();
};
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.