_Algorithm Alley_
by John Boyer


Figure 1:

Input:  Graph G, vertices S (start), T (terminate)
Declare:  H (initially empty heap)
1: For all vertices v
2:    if v == S then v.cost := 0
3:    else v.cost := infinity
3:    Insert v into H
4: Repeat
5:    M := ExtractMin(H)
6:    For each vertex A attached to M
7:       w := cost of edge from M to A
8:       if (M.cost + w < A.cost)
9:          Decrease A's Key to (M.cost + w)
10:         A.backlink := M
11: Until M = T
12: Output T.cost
13: Output vertices on chain of backlinks from T to S



Listing One
//=====================================================================
// ExtractMin() - O(n) worst-case actual; O(lg n) amortized
//=====================================================================

FibHeapNode *FibHeap::ExtractMin()
{
FibHeapNode *Result;
FibHeap *ChildHeap = NULL;

// Remove minimum node and set MinRoot to next node
     if ((Result = Minimum()) == NULL)
          return NULL;
     MinRoot = Result->Right;
     Result->Right->Left = Result->Left;
     Result->Left->Right = Result->Right;
     Result->Left = Result->Right = NULL;

     NumNodes --;
     if (Result->Mark) {
     NumMarkedNodes --;
         Result->Mark = 0;
     }
     Result->Degree = 0;

// Attach child list of Minimum node to the root list of the heap
// If there is no child list, then do no work
     if (Result->Child == NULL) {
     if (MinRoot == Result)
         MinRoot = NULL;
     }
// If MinRoot==Result then there was only one root tree, so the root list is
// the child list of that node (NULL if this is the last node in the list)
     else if (MinRoot == Result)
         MinRoot = Result->Child;
// If MinRoot is different, then the child list is pushed into a new temporary
// heap, which is then merged by Union() onto the root list of this heap.
     else {
         ChildHeap = new FibHeap();
         ChildHeap->MinRoot = Result->Child;
     }
// Complete the disassociation of the Result node from the heap
     if (Result->Child != NULL)
     Result->Child->Parent = NULL;
     Result->Child = Result->Parent = NULL;
// If there was a child list, then we now merge it with rest of the root list
     if (ChildHeap)
         Union(ChildHeap);
// Consolidate heap to find new minimum and do reorganize work
     if (MinRoot != NULL)
         _Consolidate();
// Return the minimum node, which is now disassociated with the heap
// It has Left, Right, Parent, Child, Mark and Degree cleared.
     return Result;
}
//====================================================================
// Consolidate(). Internal function that reorganizes heap as part of an 
// ExtractMin(). We must find new minimum in heap, which could be anywhere 
// along the root list. The search could be O(n) since all nodes could be on
// the root list. So, we reorganize the tree into more of a binomial forest 
// structure, and then find the new minimum on the consolidated O(lg n) sized 
// root list, and in the process set each Parent pointer to NULL,
// and count the number of resulting subtrees.
// After a list of n inserts, there will be n nodes on the root list,
// so the first ExtractMin() will be O(n) regardless of whether or not we 
// consolidate. However, the consolidation causes subsequent ExtractMin() 
// operations to be O(lg n). Furthermore, the extra cost of the first 
// ExtractMin() is covered by the higher amortized cost of Insert(), which is 
// the real governing factor in how costly the first ExtractMin() will be.
//=====================================================================
void FibHeap::_Consolidate()
{
FibHeapNode *x, *y, *w;
FibHeapNode *A[1+8*sizeof(long)]; // 1+lg(n)
int  I=0, Dn = 1+8*sizeof(long);
short d;

// Initialize the consolidation detection array
     for (I=0; I < Dn; I++)
          A[I] = NULL;
// We need to loop through all elements on root list.  When a collision of 
// degree is found, the two trees are consolidated in favor of the one with 
// the lesser element key value. We first need to break the circle so that we 
// can have a stopping condition (we can't go around until we reach the tree 
// we started with because all root trees are subject to becoming a child 
// during the consolidation).
     MinRoot->Left->Right = NULL;
     MinRoot->Left = NULL;
     w = MinRoot;

     do {
    x = w;
        d = x->Degree;
        w = w->Right;
// We need another loop here because the consolidated result
// may collide with another large tree on the root list.
        while (A[d] != NULL) {
             y = A[d];
         if (*y < *x)
         _Exchange(x, y);
             if (w == y) w = y->Right;
             _Link(y, x);
             A[d] = NULL;
             d++;
    }
    A[d] = x;
     } while (w != NULL);
// Now we rebuild the root list, find the new minimum, set all root list 
// nodes' parent pointers to NULL and count the number of subtrees.
     MinRoot = NULL;
     NumTrees = 0;
     for (I = 0; I < Dn; I++)
          if (A[I] != NULL)
              _AddToRootList(A[I]);
}
//=====================================================================
void FibHeap::_AddToRootList(FibHeapNode *x)
{
     if (x->Mark) NumMarkedNodes --;
     x->Mark = 0;
     NumNodes--;
     Insert(x);
}
//==== Node y is moved from the root list to become a subtree of node x. ====
void FibHeap::_Link(FibHeapNode *y, FibHeapNode *x)
{
// Remove node y from root list
     if (y->Right != NULL)
     y->Right->Left = y->Left;
     if (y->Left != NULL)
         y->Left->Right = y->Right;
     NumTrees--;
// Make node y a singleton circular list with a parent of x
     y->Left = y->Right = y;
     y->Parent = x;
// If node x has no children, then list y is its new child list
     if (x->Child == NULL)
     x->Child = y;
// Otherwise, node y must be added to node x's child list
     else {
         y->Left = x->Child;
         y->Right = x->Child->Right;
         x->Child->Right = y;
         y->Right->Left = y;
     }
// Increase the degree of node x because it's now a bigger tree
     x->Degree ++;
// Node y has just been made a child, so clear its mark
     if (y->Mark) NumMarkedNodes--;
     y->Mark = 0;
}


Listing Two
//=====================================================================
// DecreaseKey() - O(lg n) actual; O(1) amortized
// The O(lg n) actual cost stems from the fact that the depth, and
// therefore the number of ancestor parents, is bounded by O(lg n).
//=====================================================================

int  FibHeap::DecreaseKey(FibHeapNode *theNode, FibHeapNode& NewKey)
{
FibHeapNode *theParent;

     if (theNode==NULL || *theNode < NewKey)
         return NOTOK;
     *theNode = NewKey;

     theParent = theNode->Parent;
     if (theParent != NULL && *theNode < *theParent) {
         _Cut(theNode, theParent);
         _CascadingCut(theParent);
     }
     if (*theNode < *MinRoot)
         MinRoot = theNode;
     return OK;
}
//==== Remove node x from the child list of its parent node y ====
void FibHeap::_Cut(FibHeapNode *x, FibHeapNode *y)
{
     if (y->Child == x)
         y->Child = x->Right;
     if (y->Child == x)
     y->Child = NULL;
     y->Degree --;

     x->Left->Right = x->Right;
     x->Right->Left = x->Left;

     _AddToRootList(x);
}
//=====================================================================
// Cuts each node in parent list, putting successive ancestor nodes on the root
// list until we either arrive at the root list or until we find an ancestor 
// that is unmarked. When a mark is set (which only happens during a cascading
// cut), it means that one child subtree has been lost; if a second subtree is
// lost later during another cascading cut, then we move the node to the root 
// list so that it can be re-balanced on the next consolidate.
//=====================================================================

void FibHeap::_CascadingCut(FibHeapNode *y)
{
FibHeapNode *z = y->Parent;

     while (z != NULL) {
         if (y->Mark == 0) {
             y->Mark = 1;
             NumMarkedNodes++;
             z = NULL;
         } else {
             _Cut(y, z);
             y = z;
         z = y->Parent;
         }
     }
}




