Dijkstra's Algorithm for Network Optimization Using Fibonacci Heaps

• Download source code - 1.29 MB

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

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.

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:

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.