0

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.............

3
Contributors
3
Replies
5
Views
9 Years
Discussion Span
Last Post by rukshenaa
0

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

0

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();
};
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.