Click here to Skip to main content
15,867,765 members
Articles / Programming Languages / C++

Dijkstra's Algorithm for Network Optimization Using Fibonacci Heaps

Rate me:
Please Sign up or sign in to vote.
4.41/5 (15 votes)
23 Sep 2009CPOL5 min read 82.8K   3.3K   39   33
This article presents the Fibonacci Heap data structure and shows how to use it for graph optimization.

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

C++
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).

    C++
    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;
    }
  • 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).

    C++
    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();
            minRoot->addSibling(vertex);        
        }
        // 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.

    C++
    Node* FibonacciHeap::findMin()
    {
        return minRoot;
    }
  • Link
  • 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).

    C++
    bool FibonacciHeap::link(Node* root)
    {
        // Insert Vertex into root list
        if(rootListByRank[root->rank] == NULL)
        {
            rootListByRank[root->rank] = root;
            return false;
        }
        else
        {
            // Link the two roots
            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;
        }
    }
  • 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).

    C++
    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();
            minRoot->addSibling(temp);
            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;        
            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:

  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.

C++
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];
        Node* headOfCurrentEdge = currentEdge->tail;

        if(headOfCurrentEdge->state != SCANNED)
            {
            if(headOfCurrentEdge->state == UNLABELED)
            {
                // Insert a vertex with infinite key
                headOfCurrentEdge->state = LABELED;
                headOfCurrentEdge->pred = v;
                headOfCurrentEdge->key = v->key + currentEdge->length;
                heap->insertVertex(headOfCurrentEdge);
            }
            else if(headOfCurrentEdge->key > v->key + currentEdge->length )
            {
                // decrease the key of a vertex with finite key
                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:

C++
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


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

Comments and Discussions

 
Question4th Column of .dat file Pin
Ridzuan199028-Dec-14 20:34
Ridzuan199028-Dec-14 20:34 
Suggestionthis == NULL Pin
kaveh09625-Nov-14 12:48
kaveh09625-Nov-14 12:48 
QuestionData file Pin
Nikhil Sreekumar15-Feb-14 15:12
Nikhil Sreekumar15-Feb-14 15:12 
Questiondata problem Pin
Member 1021845019-Aug-13 6:57
Member 1021845019-Aug-13 6:57 
Bugmay be a bug in node initialize (wrong init key value) ??? Pin
lordrings26-Apr-13 16:55
lordrings26-Apr-13 16:55 
GeneralRe: may be a bug in node initialize (wrong init key value) ??? Pin
Nikhil Sreekumar15-Feb-14 15:32
Nikhil Sreekumar15-Feb-14 15:32 
QuestionHow to use the DAT file Pin
Member 968795915-Dec-12 6:55
Member 968795915-Dec-12 6:55 
QuestionDAT File Pin
Member 968795915-Dec-12 6:43
Member 968795915-Dec-12 6:43 
Questionproblem Pin
milad0078-Jul-12 8:31
milad0078-Jul-12 8:31 
QuestionProblem Pin
seddikdaya31-Dec-11 12:05
seddikdaya31-Dec-11 12:05 
QuestionDelete items after creation Pin
xumepoc20-Dec-11 4:59
xumepoc20-Dec-11 4:59 
AnswerRe: Delete items after creation Pin
xumepoc29-Jan-12 2:12
xumepoc29-Jan-12 2:12 
Questioni got a question Pin
Anonyzhang10-Dec-11 23:25
Anonyzhang10-Dec-11 23:25 
AnswerRe: i got a question Pin
max300011-Dec-11 6:18
max300011-Dec-11 6:18 
Questiondebbug prblem Pin
ham_guen10-Dec-11 13:37
ham_guen10-Dec-11 13:37 
AnswerRe: debbug prblem Pin
max300011-Dec-11 6:12
max300011-Dec-11 6:12 
GeneralRe: debbug prblem Pin
ham_guen11-Dec-11 6:23
ham_guen11-Dec-11 6:23 
GeneralRe: debbug prblem Pin
max300011-Dec-11 7:05
max300011-Dec-11 7:05 
GeneralRe: debbug prblem Pin
ham_guen11-Dec-11 7:21
ham_guen11-Dec-11 7:21 
GeneralRe: debbug prblem Pin
ham_guen11-Dec-11 8:01
ham_guen11-Dec-11 8:01 
QuestionModification to find shortest distance for all pair of nodes Pin
Nishtha Kapoor29-Oct-11 8:54
Nishtha Kapoor29-Oct-11 8:54 
QuestionStart Node problem Pin
xumepoc1-Oct-11 21:26
xumepoc1-Oct-11 21:26 
AnswerRe: Start Node problem Pin
max30003-Oct-11 8:10
max30003-Oct-11 8:10 
GeneralRE:Re: Start Node problem Pin
xumepoc3-Oct-11 9:27
xumepoc3-Oct-11 9:27 
GeneralRe: RE:Re: Start Node problem Pin
max30004-Oct-11 7:50
max30004-Oct-11 7:50 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.