_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;
}
}
}