## Introduction

This article introduces a powerful data structure in network optimization – Fibonacci Heaps. First, consider a common binary heap, where every node as at most two children, which must both have a lesser key value. For Fibonacci Heaps, we reject this restriction. So every node can have any number of children. Furthermore, there exists no single root element, but a list of roots, whereas the root with the minimum key is distinguished by a head pointer.

This special heap also has different operations, which are in general not as expensive as for binary heaps. The operations *decrease_key*, *make_heap*, *insert*, and *meld *can be done in time O(1). The most time-consuming operation is *delete_min* in time O(log n).

This article should also present the usage of Fibonacci Heaps for a faster implementation of Dijkstra's algorithm for network optimization.

## Fibonacci Heaps in detail

First, let us define a Fibonacci Heap:

*A Fibonacci Heap is a Heap with a list of root elements. Every node in the heap can have any number of children. Elements are sorted in heap-order: a node does not have a greater key value than the lowest key of its children.*

### How does a node look like?

Which requirements do we have for a single node of the heap?

For comparison: in a binary heap, every node has 4 pointers: 1 to its parent, 2 to its children, and 1 to the data.

Since we have an unknown number of children in Fibonacci heaps, we have to arrange the children of a node in a linked list. So, we need at most two pointers to the siblings of every node. This results in a linear double-linked list. Now, we need another pointer to any node of the children list and to the parent of every node. All in all, there are 5 pointers:

- left sibling
- right sibling
- parent
- children
- data

Furthermore, we define a *rank *for every node, which says how many children a node has.

Now, consider the operations for such a node element which are required for the Fibonacci heap implementation.

### Heap node operations

Now, we are ready to implement the node operations.

The required operations are:

- AddChild
Adds a child node to the current node by inserting it into the children list and linking it. This operation is done in time O(1).

- AddSibling
Adds a node into the children list the current node belongs to. This is done in time O(1) too.

- Remove
Removes the node from the sibling list and refreshes the affected pointers. This is also done in time O(1).

bool Node::addChild(Node *node)
{
if(children != NULL)
children->addSibling(node);
else
{
children = node;
node->parent = this;
rank = 1;
}
return true;
}
bool Node::addSibling(Node *node)
{
Node* temp = rightMostSibling();
if(temp == NULL)
return false;
temp->rightSibling = node;
node->leftSibling = temp;
node->parent = this->parent;
node->rightSibling = NULL;
if(parent)
parent->rank++;
return true;
}
bool Node::remove()
{
if(parent)
{
parent->rank--;
if(leftSibling)
parent->children = leftSibling;
else if(rightSibling)
parent->children = rightSibling;
else
parent->children = NULL;
}
if(leftSibling)
leftSibling->rightSibling = rightSibling;
if(rightSibling)
rightSibling->leftSibling = leftSibling;
leftSibling = NULL;
rightSibling = NULL;
parent = NULL;
return true;
}

### Fibonacci Heap operations

Now the Fibonacci Heap can be implemented. The tree of nodes is accessed by a distinguished pointer to the node with the lowest value. This element is located in the root list and has no parent. Otherwise, the heap-order would be violated.

The basic operations are:

- insertNode
Inserts a node into the root list and checks whether its value is lower than the currently lowest node and changes the access pointer if necessary. The time for this operation is O(1).

bool FibonacciHeap::insertVertex(Node * node)
{
if(node == NULL)
return false;
if(minRoot == NULL)
minRoot = node;
else
{
minRoot->addSibling(node);
if(minRoot->key > node->key)
minRoot = node;
}
return true;
}

DecreaseKeyDecreases the value of a specified node. Then the node is removed from its sibling list and is inserted into the root list. At least, it is checked whether the access pointer needs to be changed. This operation needs time O(1).

void FibonacciHeap::decreaseKey(double delta, Node* vertex)
{
vertex->key = delta;
if(vertex->parent != NULL) {
vertex->remove();
minRoot->addSibling(vertex);
}
if(vertex->key < minRoot->key)
minRoot = vertex;
}

FindMinReturns the node referenced by the access pointer. This is the node with the minimum key.

Node* FibonacciHeap::findMin()
{
return minRoot;
}

LinkChecks if two nodes in the root list have the same rank. If yes, the node with the higher key is moved into the children list of the other node. This step is done in time O(1).

bool FibonacciHeap::link(Node* root)
{
if(rootListByRank[root->rank] == NULL)
{
rootListByRank[root->rank] = root;
return false;
}
else
{
Node* linkVertex = rootListByRank[root->rank];
rootListByRank[root->rank] = NULL;
if(root->key < linkVertex->key || root == minRoot)
{
linkVertex->remove();
root->addChild(linkVertex);
if(rootListByRank[root->rank] != NULL)
link(root);
else
rootListByRank[root->rank] = root;
}
else
{
root->remove();
linkVertex->addChild(root);
if(rootListByRank[linkVertex->rank] != NULL)
link(linkVertex);
else
rootListByRank[linkVertex->rank] = linkVertex;
}
return true;
}
}

DeleteMinCopies all children of the node referenced by the access pointer into the root list. After each insertion, a linking step is done if necessary. At least the minimum element is deleted, and the node with the minimum key is determined. The amortized time depends on the count of children of the minimum node. In the worst case, for each child, a removing, inserting, and linking operation required. This takes time O(log n).

Node* FibonacciHeap::deleteMin()
{
Node *temp = minRoot->children->leftMostSibling();
Node *nextTemp = NULL;
while(temp != NULL)
{
nextTemp = temp->rightSibling; temp->remove();
minRoot->addSibling(temp);
temp = nextTemp;
}
temp = minRoot->leftMostSibling();
if(temp == minRoot)
{
if(minRoot->rightSibling)
temp = minRoot->rightSibling;
else
{
Node* out = minRoot;
minRoot->remove();
minRoot = NULL;
return out;
}
}
Node* out = minRoot;
minRoot->remove();
minRoot = temp;
for(int i=0; i<100; i++)
rootListByRank[i] = NULL;
while(temp)
{
if(temp->key < minRoot->key)
{
minRoot = temp;
}
nextTemp = temp->rightSibling;
link(temp);
temp = nextTemp;
}
return out;
}

Now we have implemented all the necessary operations for the Dijkstra's algorithm we will discuss in the next part.

## Dijkstra's algorithm using Fibonacci Heaps

### The concept of Dijkstra

Dijkstra's algorithm works the following way. Beginning at the target vertex, it checks for each vertex, which has an incoming edge to the current one; if the path over the current vertex is shorter than the previously found one, it replaces it. Then, the same operation is done for this vertex. The algorithm is aborted when all vertices have been scanned. This operation is called *scan* for the following reason.

To summarize, a *scan* can be described by these steps:

- Find all vertices, which are the head of an edge, whose tail is the current node.
- For each of these vertices, check whether the best found way can be improved by going the way over the current vertex and the edge between these vertices.

### Implementation of Dijkstra's algorithm

The actual Dijkstra algorithm is very simple. Beginning with the source vertex, we do a *scan *and mark the vertex as scanned. Then, we repeat this step with the vertices which have an edge with the head on the source vertex. Then, we repeat the *scan *for all vertices which have an edge to the last scanned vertex.

During the algorithm, a node can have three states: `LABELED`

, `UNLABELED`

, and `SCANNED`

. Nodes are marked labels when the shortest path to the target is found. A node is unlabeled when there is no path found yet (initial state), and labeled when a path is found, but when maybe a shorter one exists.

FibonacciHeap* heap = new FibonacciHeap();
heap->insertVertex(vertices[n-1]);
bool abort = false;
long j = 0;
do
{
Node* v = heap->deleteMin();
v->state = SCANNED;
for(int i = 0; i < v->incomingEdges.size(); i++)
{
Edge* currentEdge = v->incomingEdges[i];
Node* headOfCurrentEdge = currentEdge->tail;
if(headOfCurrentEdge->state != SCANNED)
{
if(headOfCurrentEdge->state == UNLABELED)
{
headOfCurrentEdge->state = LABELED;
headOfCurrentEdge->pred = v;
headOfCurrentEdge->key = v->key + currentEdge->length;
heap->insertVertex(headOfCurrentEdge);
}
else if(headOfCurrentEdge->key > v->key + currentEdge->length )
{
headOfCurrentEdge->pred = v;
heap->decreaseKey(v->key + currentEdge->length, headOfCurrentEdge);
}
}
}
}
while(!heap->isEmpty());

After this algorithm, we have the predecessor for every node in the `pred`

pointer. This points to the next vertex of the shortest path to the target. The result is that we have the shortest path to the target for every vertex. We just have to follow the predecessors:

while(temp)
{
printf("%d", temp->data);
temp = temp->pred;
if(temp)
printf(" - ");
}

This structure is called *shortest path tree*, because it looks like a tree with the target vertex as root. For every node, we get a parent by the predecessor in that tree.

Since 2006 I study technical mathematics at Dresden University of Technology and since 2008 I work than working student at SAP Research in Dresden. My programming interests are developing and implementing algorithms for solving mathematical problems in C/C++, especially optimization.