DSA Dijkstra’s Algorithm

Welcome to TheCodingCollege.com! In this post, we’ll explore Dijkstra’s Algorithm, one of the most popular algorithms for finding the shortest path in a graph. This algorithm is a cornerstone of Data Structures and Algorithms (DSA), with applications in network routing, navigation systems, and more.

What is Dijkstra’s Algorithm?

Dijkstra’s Algorithm finds the shortest path from a single source node to all other nodes in a graph with non-negative edge weights. It uses a greedy approach, ensuring that once a node’s shortest distance is determined, it remains unchanged.

Key Characteristics of Dijkstra’s Algorithm

1. Non-negative Edge Weights: Cannot handle negative weight edges.
2. Graph Type: Works on both directed and undirected graphs.
3. Greedy Approach: Chooses the shortest known path at each step.

Algorithm Workflow

1. Initialize distances of all vertices to infinity (∞\infty), except the source vertex, which is set to 0.
2. Use a priority queue to explore the vertex with the smallest distance.
3. For the current vertex, update the distances of its neighbors if a shorter path is found.
4. Repeat until all vertices are processed or the target vertex is reached.

Steps of Dijkstra’s Algorithm

1. Initialization:
   • Distance to source = 0, other vertices = ∞\infty.
   • Priority queue contains the source vertex with distance 0.
2. Relaxation:
   • For each vertex, update the shortest path for its neighbors if a better path is found.
3. Termination:
   • The algorithm terminates when all vertices have been processed.

Implementation in Python

Here’s a Python implementation of Dijkstra’s Algorithm using a priority queue:

import heapq

def dijkstra(graph, source, vertices):
    # Initialize distances and priority queue
    distances = {i: float('inf') for i in range(vertices)}
    distances[source] = 0
    priority_queue = [(0, source)]  # (distance, vertex)
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        # Skip if this distance is not the shortest
        if current_distance > distances[current_vertex]:
            continue
        
        # Explore neighbors
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Example Usage
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}
source = 0
vertices = 4
shortest_paths = dijkstra(graph, source, vertices)
print("Shortest paths:", shortest_paths)

Dry Run Example

Graph Example

• Vertices: 0,1,2,30, 1, 2, 3
• Edges:
  • (0,1,4)(0, 1, 4)
  • (0,2,1)(0, 2, 1)
  • (2,1,2)(2, 1, 2)
  • (1,3,1)(1, 3, 1)
  • (2,3,5)(2, 3, 5)

Step-by-Step Execution

1. Initialize distances: [0,∞,∞,∞][0, \infty, \infty, \infty].
2. Explore 00: Update distances to 11 (4) and 22 (1).
3. Explore 22: Update distance to 11 (3) and 33 (6).
4. Explore 11: Update distance to 33 (4).
5. Final distances: [0,3,1,4][0, 3, 1, 4].

Applications of Dijkstra’s Algorithm

1. Navigation Systems: Finding the shortest route on maps.
2. Network Routing: Optimizing data packet paths.
3. Flight Scheduling: Computing the least expensive or fastest routes.
4. Robot Navigation: Pathfinding in obstacle-filled environments.

Limitations

1. Negative Weights: Fails in graphs with negative edge weights.
   • Use Bellman-Ford Algorithm for such graphs.
2. High Complexity: The time complexity is O((V+E)log⁡V)O((V + E) \log V), which can be slow for dense graphs.

Optimizations

1. Binary Heap: Efficient priority queue implementation reduces complexity.
2. Fibonacci Heap: Further optimization to O(E+Vlog⁡V)O(E + V \log V).

Comparison with Other Algorithms

Conclusion

Dijkstra’s Algorithm is a powerful tool for solving shortest path problems in graphs with non-negative weights. Its efficiency and simplicity make it a go-to choice for numerous real-world applications.