Article

Dijkstra's Algorithm for Network Optimization Using Fibonacci Heaps

By , 23 Sep 2009
 Rate this:

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:

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

• 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)
else
{
children = node;
node->parent = this;
rank = 1;
}

return true;
}

{
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
{
if(minRoot->key > node->key)
minRoot = node;
}
return true;
}```
• DecreaseKey
• Decreases 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) // The vertex has a parent
{
// Remove vertex and add to root list
vertex->remove();
}
// Check if key is smaller than the key of minRoot
if(vertex->key < minRoot->key)
minRoot = vertex;
}```
• FindMin
• Returns the node referenced by the access pointer. This is the node with the minimum key.

```Node* FibonacciHeap::findMin()
{
return minRoot;
}```
• Checks 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)
{
// Insert Vertex into root list
if(rootListByRank[root->rank] == NULL)
{
rootListByRank[root->rank] = root;
return false;
}
else
{
rootListByRank[root->rank] = NULL;

if(root->key < linkVertex->key || root == minRoot)
{
if(rootListByRank[root->rank] != NULL)
else
rootListByRank[root->rank] = root;
}
else
{
root->remove();
else
}
return true;
}
}```
• DeleteMin
• Copies 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;

// Adding Children to root list
while(temp != NULL)
{
nextTemp = temp->rightSibling; // Save next Sibling
temp->remove();
temp = nextTemp;
}

// Select the left-most sibling of minRoot
temp = minRoot->leftMostSibling();

// Remove minRoot and set it to any sibling, if there exists one
if(temp == minRoot)
{
if(minRoot->rightSibling)
temp = minRoot->rightSibling;
else
{
// Heap is obviously empty
Node* out = minRoot;
minRoot->remove();
minRoot = NULL;
return out;
}
}
Node* out = minRoot;
minRoot->remove();
minRoot = temp;

// Initialize list of roots
for(int i=0; i<100; i++)
rootListByRank[i] = NULL;

while(temp)
{
// Check if key of current vertex is smaller than the key of minRoot
if(temp->key < minRoot->key)
{
minRoot = temp;
}

nextTemp = temp->rightSibling;
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:

1. Find all vertices, which are the head of an edge, whose tail is the current node.
2. 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;
// Scan
do
{
// Delete minimum path
Node* v = heap->deleteMin();

v->state = SCANNED;

for(int i = 0; i < v->incomingEdges.size(); i++)
{
Edge* currentEdge = v->incomingEdges[i];

{
{
// Insert a vertex with infinite key
}
else if(headOfCurrentEdge->key > v->key + currentEdge->length )
{
// decrease the key of a vertex with finite key
}
}
}
}
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.

Software Developer (Junior) SAP Research
Germany
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.

 First PrevNext
 Data file [modified] Nikhil Sreekumar 15-Feb-14 15:12
 data problem Member 10218450 19-Aug-13 6:57
 may be a bug in node initialize (wrong init key value) ??? lordrings 26-Apr-13 16:55
 How to use the DAT file Member 9687959 15-Dec-12 6:55
 DAT File Member 9687959 15-Dec-12 6:43
 Problem seddikdaya 31-Dec-11 12:05
 Delete items after creation xumepoc 20-Dec-11 4:59
 Re: Delete items after creation xumepoc 29-Jan-12 2:12
 Last Visit: 31-Dec-99 18:00     Last Update: 11-Mar-14 0:20 Refresh 1234 Next »