Dijkstra’s Algorithm with Fibonacci Heaps: A Python Example

By Harshvardhan Mishra Feb 17, 2024
Dijkstra's Algorithm with Fibonacci Heaps: A Python ExampleDijkstra's Algorithm with Fibonacci Heaps: A Python Example

Dijkstra’s algorithm is a popular algorithm used to find the shortest path between nodes in a graph. When combined with Fibonacci heaps, it achieves a better time complexity compared to traditional implementations using priority queues. In this article, we will explore Dijkstra’s algorithm with Fibonacci heaps and provide a Python example with explanation.

Understanding Dijkstra’s Algorithm

Dijkstra’s algorithm is a greedy algorithm that works by iteratively selecting the node with the smallest distance from the source node and updating the distances of its neighboring nodes. It maintains a priority queue to keep track of the nodes with the smallest distances.

The algorithm starts by initializing the distances of all nodes to infinity, except for the source node which is set to 0. It then selects the node with the smallest distance from the priority queue and relaxes its neighboring nodes by updating their distances if a shorter path is found. This process continues until all nodes have been visited or the destination node is reached.

Suggested: Dancing Links (DLX): An Efficient Algorithm for Backtracking

The Advantages of Fibonacci Heaps

Traditionally, Dijkstra’s algorithm uses a priority queue to keep track of the nodes with the smallest distances. However, the time complexity of traditional priority queues can be a bottleneck in large graphs.

Fibonacci heaps, on the other hand, provide a more efficient way to implement the priority queue. They have a better amortized time complexity for the decrease key operation, which is a crucial step in Dijkstra’s algorithm. This results in an overall improvement in the time complexity of the algorithm.

Python Example

Let’s take a look at a Python implementation of Dijkstra’s algorithm with Fibonacci heaps:

import heapq

class FibonacciHeapNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.degree = 0
        self.marked = False
        self.parent = None
        self.child = None
        self.left = self
        self.right = self

    def __lt__(self, other):
        return self.key < other.key

class FibonacciHeap:
    def __init__(self):
        self.min = None
        self.num_nodes = 0

    def insert(self, key, value):
        node = FibonacciHeapNode(key, value)
        self._insert_node(node)
        return node

    def _insert_node(self, node):
        if self.min is None:
            self.min = node
        else:
            self._link(self.min, node)
            if node.key < self.min.key:
                self.min = node
        self.num_nodes += 1

    def _link(self, node1, node2):
        node1.right.left = node2
        node2.right.left = node1
        node1.right = node2
        node2.left = node1

    def extract_min(self):
        min_node = self.min
        if min_node is not None:
            child = min_node.child
            while child is not None:
                next_child = child.right
                self._insert_node(child)
                child.parent = None
                child = next_child
            self._remove_node(min_node)
            self.num_nodes -= 1
        return min_node

    def _remove_node(self, node):
        node.left.right = node.right
        node.right.left = node.left
        if node == node.right:
            self.min = None
        else:
            self.min = node.right

    def decrease_key(self, node, new_key):
        node.key = new_key
        parent = node.parent
        if parent is not None and node.key < parent.key:
            self._cut(node, parent)
            self._cascading_cut(parent)
        if node.key < self.min.key:
            self.min = node

    def _cut(self, node, parent):
        node.left.right = node.right
        node.right.left = node.left
        parent.degree -= 1
        if node == parent.child:
            parent.child = node.right
        if parent.degree == 0:
            parent.child = None
        self._insert_node(node)
        node.parent = None
        node.marked = False

    def _cascading_cut(self, node):
        parent = node.parent
        if parent is not None:
            if node.marked:
                self._cut(node, parent)
                self._cascading_cut(parent)
            else:
                node.marked = True

def dijkstra(graph, source):
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
    heap = FibonacciHeap()
    nodes = {}
    for node in graph:
        nodes[node] = heap.insert(distances[node], node)
    while heap.num_nodes > 0:
        min_node = heap.extract_min()
        current_node = min_node.value
        for neighbor, weight in graph[current_node].items():
            new_distance = distances[current_node] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heap.decrease_key(nodes[neighbor], new_distance)
    return distances

In the above code, we define two classes: FibonacciHeapNode and FibonacciHeap. The FibonacciHeapNode class represents a node in the Fibonacci heap, while the FibonacciHeap class implements the Fibonacci heap data structure.

The dijkstra function takes a graph and a source node as input and returns a dictionary of distances from the source node to all other nodes in the graph.

Suggested: Exploring Sorting Algorithms: A Comprehensive Guide to Sorting Methods

Conclusion

Dijkstra’s algorithm with Fibonacci heaps provides a more efficient way to find the shortest path between nodes in a graph. By utilizing the benefits of Fibonacci heaps, we can achieve a better time complexity compared to traditional implementations using priority queues. The Python example provided in this article demonstrates how to implement Dijkstra’s algorithm with Fibonacci heaps (read here).

Remember to import the necessary libraries and use the provided code as a starting point for your own implementations. Happy coding!

Related Post

Leave a Reply

Your email address will not be published. Required fields are marked *