Solve this Dijkstra Algorithm using heaps....

I have Dijkstra Algorithm....I m not able to compile it using fibonacci heap...I m attaching the files....Early help will be really appreciated...I m doing Uni project....

// Directed Graphs

# include <cstdio>
#include "dgraph.h"

// Constructor

DGraph::DGraph(int n)
{

  nVertices = n;

  vertices = new DGraphVertex[n];
  initVertices();

}

//Destructor

DGraph::~DGraph()
{
  clear();
  delete [] vertices;

}

// Clear all edges from the graphs

void DGraph::clear()
{
  DGraphEdge *edge, *nextEdge;
  for (int i = 0; i < nVertices; i++)
  {
    edge = vertices[i].outHead;

    while(edge) {
      nextEdge = edge->nextOut;
      delete edge;
      edge = nextEdge;
    }
  }
  initVertices();
}

void DGraph::initVertices()
{
  for(int i = 0; i < nVertices; i++)
  {
    vertices[i].outHead = vertices[i].outTail = 0;
    vertices[i].inHead = vertices[i].inTail = 0;
    vertices[i].outSize = vertices[i].inSize = 0;
  }
}

// AddnewEdge()
// Adds a new edge from vertex 'source' to vertex 'target' with a corresponding
// distance of dist.

void DGraph::addNewEdge(int source, int target, int dist)
{
  DGraphEdge *newEdge = new DGraphEdge;
  newEdge->source = source;
  newEdge->target = target;
  newEdge->dist = dist;
  newEdge->nextOut = NULL;
  newEdge->nextIn = NULL;

  DGraphVertex *vertex = &vertices[source];
  if(vertex->outTail) {
    vertex->outTail->nextOut = newEdge;
  }

  else
  {
    vertex->outHead = newEdge;
  }

  vertex->outTail = newEdge ;
  vertex->outSize++ ;

  vertex = &vertices[target];
  if(vertex->inTail)
  {
    vertex->inTail->nextIn = newEdge;
  }
  else
  {
    vertex->inHead = newEdge;
  }

  vertex->inTail = newEdge ;
  vertex->inSize++ ;

};

bool DGraph::edgeExists(int v, int w) const
{
  // Check all existing edges from v to determine whether an edge to w exists

  const DGraphEdge *edge = vertices[v].outHead;
  while(edge)
  {
    if(edge->target == w) return true;
    edge = edge->nextOut;
  }
  return false;
}

// Check whether all vertices are reachable from the source vertex s.

bool DGraph::reachable(int s) const
{
  int *stack = new int[nVertices];
  int tos = 0;

  int *visited = new int[nVertices];
  for(int i =0; i < nVertices; i++) visited[i] = 0;

  int vertexCount = 0;
  visited[s] = 1;
  stack[tos++] = s;
  DGraphEdge *edge;
  int v,w;

  while(tos)
  {
    v = stack[--tos];
    vertexCount++;
    edge = vertices[v].outHead;

    while(edge)
    {
      w = edge->target;
      if(!visited[w])
      {
        visited[w] = 1;
        stack[tos++] = w;
      }
      edge = edge->nextOut;
    }
  }

  delete [] stack;

  delete [] visited;

  return vertexCount == nVertices;
}

// Print a text representation of the graph to the standard output

void DGraph::print() const
{
  const DGraphEdge *edge;

  printf("Graph (vertex: edge list) = \n");

  for (int i = 0; i < nVertices; i++)
  {
    printf("%d: ", i);
    edge = vertices[i].outHead;
    while(edge)
    {
      printf(" %d", edge->target);
      edge = edge->nextOut;
    }
    putchar('\n');
  }

  printf("Graph (vertex: edge{dist} list) = \n");

  for(int  i = 0; i < nVertices; i++)
  {
    printf("%d: ", i);
    edge = vertices[i].outHead;
    while(edge)
    {
      printf(" %d{%d}", edge->target, edge->dist);
      edge = edge->nextOut;
    }
    putchar('\n');
  }
}

#include "dijkstra.h"
#include "dgraph.h"
#include "fheap.h"

// Constructor

// Allocate the algorithm for use on graph of n vertices. The parameter heap D(points
// to heap descriptor object) specifies then heap to be used by Dijkstra's Algorithm

Dijkstra::Dijkstra(int n, HeapDesc *heapD)
{

  heap = heapD->newInstance (n);
  s = new bool [n];
  f = new bool [n];

}

// Destructor

Dijkstra::~Dijkstra()
{

  delete [] s;
  delete [] f;
  delete heap;

}

// init ()
// Initialize the algorithm for use with the graph pointed to by g.

void Dijkstra::init(const DGraph *g)
{

  graph = g;

}

// run()
// Run the algorithm, computing single-source from the starting vertex v0.
// This assumes that array has been initialized with d[v] = INFINITE_DIST for all
// vertices v ! = v0

void Dijkstra::run(long *d, int v0)
{

  //Indexes counters and pointers

  int v, w;
  long dist;
  const DGraphEdge *edge;

  // Initialisation

  // Optimise access to the data structure allocated for the algorithm

  const int n = graph->nVertices;
  const DGraphVertex *vertices = graph->vertices;

  // Algorithm

  // Initialise all vertices as unexplored

  for (v = 0; v < n; v++) s[v] = false;
  for (v = 0; v < n; v++) f[v] = false;

  // Place v0 into the frontier set with a distance of zero

  d[v0] = 0;
  heap->insert(v0, 0);
  f[v0] = true;

// Repeatedly update distances from the minimum remaining trigger vertex

while(heap->nItems () > 0)
{

  // Delete the Vertex in frontier that has minimum distance

  v = heap->deleteMin ();

  // The selected vertex moves from the frontier to the solution set

  s[v] = true;
  f[v] = false;

  // explore the OUT set of V

  edge = vertices[v].outHead;
  while(edge)
  {

    w = edge->target;

    if(s[w] == false)
    {

      dist = d[v] + edge->dist;
        if(dist < d[w])
        {
          d[w] = dist;
          if(f[w])
          {
          heap->decreaseKey(w, dist);
        }

        else
        {
          heap->insert(w, dist);
          f[w] = true;
        }
    }
  }

  edge = edge->nextOut;

}// end of while
} // while
}


#include <cstdlib>
#include <cmath>
#if FHEAP_DUMP
#include <cstdio>
#endif
#include "fheap.h"

/*--- FHeap (public methods) ------------------------------------------------*/

/* --- Constructor ---
 * Creates an FHeap object capable of holding up to $n$ items.
 */
FHeap::FHeap(int n)
{
    int i;
#if FHEAP_DUMP
printf("new, ");
#endif
    maxTrees = 1 + (int)(1.44 * log(n)/log(2.0));
    maxNodes = n;

    trees = new (FHeapNode *)[maxTrees];
    for(i = 0; i < maxTrees; i++) trees[i] =0;

    nodes = new (FHeapNode *)[n];
    for(i = 0; i < n; i++) nodes[i] = 0;

    itemCount = 0;

    /* The $treeSum$ of the heap helps to keep track of the maximum rank while
     * nodes are inserted or deleted.
     */
    treeSum = 0;

    /* For experimental purposes, we keep a count of the number of key
     * comparisons.
     */
    compCount = 0;

#if FHEAP_DUMP
printf("new-exited, ");
#endif
}

/* --- Destructor ---
 */
FHeap::~FHeap()
{
    int i;

#if FHEAP_DUMP
printf("delete, ");
#endif

    for(i = 0; i < maxNodes; i++) delete nodes[i];
    delete [] nodes;
    delete [] trees;

#if FHEAP_DUMP
printf("delete-exited, ");
#endif
}

/* --- insert() ---
 * Inserts an item $item$ with associated key $k$ into the heap.
 */
void FHeap::insert(int item, long k)
{
    FHeapNode *newNode;

#if FHEAP_DUMP
printf("insert, ");
#endif

    /* create an initialise the new node */
    newNode = new FHeapNode;
    newNode->child = NULL;
    newNode->left = newNode->right = newNode;
    newNode->rank = 0;
    newNode->item = item;
    newNode->key = k;

    /* maintain a pointer to $item$'s new node in the heap */
    nodes[item] = newNode;

    /* meld the new node into the heap */
    meld(newNode);

    /* update the heaps node count */
    itemCount++;

#if FHEAP_DUMP
printf("insert-exited, ");
#endif
}

/* --- deleteMin() ---
 * Deletes and returns the minimum item from the heap.
 */
int FHeap::deleteMin()
{
    FHeapNode *minNode, *child, *next;
    long k, k2;
    int r, v, item;

#if FHEAP_DUMP
printf("deleteMin, ");
#endif

    /* First we determine the maximum rank in the heap. */
    v = treeSum;
    r = -1;
    while(v) {
        v = v >> 1;
        r++;
    };

    /* Now determine which root node is the minimum. */
    minNode = trees[r];
    k = minNode->key;
    while(r > 0) {
        r--;
        next = trees[r];
        if(next) {
            if((k2 = next->key) < k) {
                k = k2;
                minNode = next;
            }
            compCount++;
        }
    }

    /* We remove the minimum node from the heap but keep a pointer to it. */
    r = minNode->rank;
    trees[r] = NULL;
    treeSum -= (1 << r);

    child = minNode->child;
    if(child) meld(child);

    /* Record the vertex no of the old minimum node before deleting it. */
    item = minNode->item;
    nodes[item] = NULL;
    delete minNode;
    itemCount--;

#if FHEAP_DUMP
printf("deleteMin-exited, ");
#endif

    return item;
}

/* --- decreaseKey() ---
 * Decreases the key used for item $item$ to the value newValue.  It is left
 * for the user to ensure that newValue is in-fact less than the current value
 */
void FHeap::decreaseKey(int item, long newValue)
{
    FHeapNode *cutNode, *parent, *newRoots, *r, *l;
    int prevRank;

#if FHEAP_DUMP
printf("decreaseKey on vn = %d, ", item);
#endif

    /* Obtain a pointer to the decreased node and its parent then decrease the
     * nodes key.
     */
    cutNode = nodes[item];
    parent = cutNode->parent;
    cutNode->key = newValue;

    /* No reinsertion occurs if the node changed was a root. */
    if(!parent) {
#if FHEAP_DUMP
printf("decreaseKey-exited, ");
#endif
        return;
    }

    /* Update the left and right pointers of cutNode and its two neighbouring
     * nodes.
     */
    l = cutNode->left;
    r = cutNode->right;
    l->right = r;
    r->left = l;
    cutNode->left = cutNode->right = cutNode;

    /* Initially the list of new roots contains only one node. */
    newRoots = cutNode;

    /* While there is a parent node that is marked a cascading cut occurs. */
    while(parent && parent->marked) {

        /* Decrease the rank of cutNode's parent and update its child pointer.
         */
        parent->rank--;
        if(parent->rank) {
            if(parent->child == cutNode) parent->child = r;
        }
        else {
            parent->child = NULL;
        }

        /* Update the cutNode and parent pointers to the parent. */
        cutNode = parent;
        parent = cutNode->parent;

        /* Update the left and right pointers of cutNodes two neighbouring
         * nodes.
         */
        l = cutNode->left;
        r = cutNode->right;
        l->right = r;
        r->left = l;

        /* Add cutNode to the list of nodes to be reinserted as new roots. */
        l = newRoots->left;
        newRoots->left = l->right = cutNode;
        cutNode->left = l;
        cutNode->right = newRoots;
        newRoots = cutNode;
    }

    /* If the root node is being relocated then update the trees[] array.
     * Otherwise mark the parent of the last node cut.
     */
    if(!parent) {
        prevRank = cutNode->rank + 1;
        trees[prevRank] = NULL;
        treeSum -= (1 << prevRank);
    }
    else {
        /* Decrease the rank of cutNode's parent an update its child pointer.
         */
        parent->rank--;
        if(parent->rank) {
            if(parent->child == cutNode) parent->child = r;
        }
        else {
            parent->child = NULL;
        }

        parent->marked = 1;
    }

    /* Meld the new roots into the heap. */
    meld(newRoots);

#if FHEAP_DUMP
printf("decreaseKey-exited, ");
#endif
}

/*--- FHeap (private methods) -----------------------------------------------*/

/* --- meld() ---
 * melds the linked list of trees pointed to by $treeList$ into the heap.
 */
void FHeap::meld(FHeapNode *treeList)
{
    FHeapNode *first, *next, *nodePtr, *newRoot, *temp, *temp2, *lc, *rc;
    int r;

#if FHEAP_DUMP
printf("meld: ");
#endif

    /* We meld each tree in the circularly linked list back into the root level
     * of the heap.  Each node in the linked list is the root node of a tree.
     * The circularly linked list uses the sibling pointers of nodes.  This
     *  makes melding of the child nodes from a deleteMin operation simple.
     */
    nodePtr = first = treeList;

    do {

#if FHEAP_DUMP
printf("%d, ", nodePtr->item);
#endif

        /* Keep a pointer to the next node and remove sibling and parent links
         * from the current node.  nodePtr points to the current node.
         */
        next = nodePtr->right;
        nodePtr->right = nodePtr->left = nodePtr;
        nodePtr->parent = NULL;

        /* We merge the current node, nodePtr, by inserting it into the
         * root level of the heap.
         */
        newRoot = nodePtr;
        r = nodePtr->rank;

        /* This loop inserts the new root into the heap, possibly restructuring
         * the heap to ensure that only one tree for each degree exists.
         */
        do {

            /* Check if there is already a tree of degree r in the heap.
             * If there is then we need to link it with newRoot so it will be
             * reinserted into a new place in the heap.
             */
            if((temp = trees[r])) {

              /* temp will be linked to newRoot and relocated so we no
                 * longer will have a tree of degree r.
                 */
                trees[r] = NULL;
                treeSum -= (1 << r);

              /* Swap temp and newRoot if necessary so that newRoot always
                 * points to the root node which has the smaller key of the
                 * two.
                 */
              if(temp->key < newRoot->key) {
                    temp2 = newRoot;
                    newRoot = temp;
                    temp = temp2;
                }
                compCount++;

                /* Link temp with newRoot, making sure that sibling pointers
                 * get updated if rank is greater than 0.  Also, increase r for
                 * the next pass through the loop since the rank of new has
                 * increased.
                 */
              if(r++ > 0) {
                    rc = newRoot->child;
                    lc = rc->left;
                    temp->left = lc;
                    temp->right = rc;
                    lc->right = rc->left = temp;
                }
                newRoot->child = temp;
                newRoot->rank = r;
                temp->parent = newRoot;
                temp->marked = 0;
            }
            /* Otherwise if there is not a tree of degree r in the heap we
             * allow newRoot, which possibly carries moved trees in the heap,
             * to be a tree of degree r in the heap.
             */
            else {

                trees[r] = newRoot;
                treeSum += (1 << r);;

                /* NOTE:  Because newRoot is now a root we ensure it is
                 *        marked.
                 */
                newRoot->marked = 1;
          }

            /* Note that temp will be NULL if and only if there was not a tree
             * of degree r.
             */
        } while(temp);

        nodePtr = next;

    } while(nodePtr != first);

#if FHEAP_DUMP
printf("meld-exited, ");
#endif
}

/*--- FHeap (debugging) -----------------------------------------------------*/

/* --- dumpNodes() ---
 * Recursively print a text representation of the node subtree starting at the
 * node poined to by $node$, using an indentationlevel of $level$.
 */
void FHeap::dumpNodes(FHeapNode *node, int level)
{
#if FHEAP_DUMP
     FHeapNode *childNode, *partner;
     int i, childCount;

     /* Print leading whitespace for this level. */
     for(i = 0; i < level; i++) printf("   ");

     printf("%d(%ld)[%d]\n", node->item, node->key, node->rank);

     if((childNode = node->child)) {
       childNode = node->child->right;

         childCount = 0;

         do {
             dumpNodes(childNode, level+1);
           if(childNode->dim > node->dim) {
                 for(i = 0; i < level+1; i++) printf("   ");
             printf("error(dim)\n");  exit(1);
           }
           if(childNode->parent != node) {
                 for(i = 0; i < level+1; i++) printf("   ");
             printf("error(parent)\n");
           }
             childNode = childNode->right;
           childCount++;
         } while(childNode != node->child->right);

         if(childCount != node->dim) {
           for(i = 0; i < level; i++) printf("   ");
             printf("error(childCount)\n");  exit(1);
         }
     }
     else {
         if(node->dim != 0) {
             for(i = 0; i < level; i++) printf("   ");
           printf("error(dim)\n"); exit(1);
       }
     }
#endif
}

/* --- dump() ---
 * Print a text representation of the heap to the standard output.
 */
void FHeap::dump() const
{
#if FHEAP_DUMP
    int i;
    FHeapNode *node;

    printf("\n");
    printf("treeSum = %d\n", treeSum);
    printf("array entries 0..maxTrees =");
    for(i = 0; i < maxTrees; i++) {
        printf(" %d", trees[i] ? 1 : 0 );
    }
    printf("\n\n");
    for(i = 0; i < maxTrees; i++) {
        if((node = trees[i])) {
            printf("tree %d\n\n", i);
            dumpNodes(node, 0);
          printf("\n");
        }
    }
    fflush(stdout);
#endif
}


/*---------------------------------------------------------------------------*/
#ifndef FHEAP_H
#define FHEAP_H

#include "heap.h"  /* Defines the base class for heaps. */


/* Option to allow printing of debugging information.  Use 1 for yes, or 0 for
 * no.
 */
#define FHEAP_DUMP 0


/* --- FHeapNode ---
 * Fibonacci heap node class.
 *
 * A nodes has the following pointers:
 * parent      - a pointer to the nodes parent node (if any).
 * child       - a pointer to a child node (typically the highest rank child).
 * left, right - sibling pointers which provide a circular doubly linked list
 *               containing all the parents nodes children.
 *
 * The remaining fields are:
 * rank        - the nodes rank, that is, the number of children it has.
 * key         - the nodes key.
 * item        - the number of the item that the node is associated with.
 */
class FHeapNode {
  public:
    FHeapNode *parent;
    FHeapNode *left, *right;
    FHeapNode *child;
    int rank;
    int marked;
    long key;
    int item;
};

/* --- FHeap ---
 * Fibonacci heap class.
 *
 * trees - An array of pointers to trees at root level in the heap.  Entry i
 *         in the array points to the root node of a tree that has nodes of
 *         dimension i on the main trunk.
 * nodes - An array of pointers to nodes in the heap.  Nodes are indexed
 *         according to their vertex number.  This array can then be used to
 *         look up the node for corresponding to a vertex number, and is
 *         useful when freeing space taken up by the heap.
 * maxNodes - The maximum number of nodes allowed in the heap.
 * maxTrees - The maximum number of trees allowed in the heap (calculated from
 *             maxNodes).
 * itemCount - The current number of nodes in the heap.
 * treeSum - The binary value represented by trees in the heap.
 *           By maintaining this it is easy to keep track of the maximum rank
 *           tree in the heap.
 * compCount - can be used for experimental purposes when counting the number
 *             of key comparisons.
 */
class FHeap: public Heap {
  public:
    FHeap(int n);
    ~FHeap();

    int deleteMin();
    void insert(int item, long k);
    void decreaseKey(int item, long newValue);
    int nItems() const { return itemCount; }

    long nComps() const { return compCount; }
    void dump() const;

  private:
    FHeapNode **trees;
    FHeapNode **nodes;
    int maxNodes, maxTrees, itemCount, treeSum;
    long compCount;

    void meld(FHeapNode *treeList);
    static void dumpNodes(FHeapNode *node, int level);
};

/*---------------------------------------------------------------------------*/
#endif

# ifndef HEAP_H
# define HEAP_H

class Heap
{
  public:
    virtual ~Heap() { };
    virtual int deleteMin() = 0;
    virtual void insert(int item, long key) = 0;
    virtual void decreaseKey(int item, long newKey) = 0;
    virtual int nItems() const = 0;
    virtual long nComps() const = 0;

};

class HeapDesc
{
  public:
    virtual ~HeapDesc() { };
    virtual Heap *newInstance(int n) const = 0;
};

template <class T>
class HeapD: public HeapDesc
{
  public:
  Heap *newInstance(int n) const { return new T(n); };
};

#endif