Dijkstra’s Algorithm (Shortest Path)

 

Dijkstra’s Algorithm (Shortest Path) 🚀

Dijkstra’s Algorithm is used to find the shortest path from a single source vertex to all other vertices in a graph with non-negative weights.

---

🔹 How It Works

✅ Input: A graph represented as an adjacency list or matrix and a starting node.
✅ Output: The shortest path distances from the source to all nodes.
✅ Time Complexity: O((V + E) log V) (using a priority queue).
✅ Uses: Greedy Approach and Min-Heap (Priority Queue) for efficiency.

---

🔹 Algorithm Steps

1️⃣ Initialize:

• Set the distance to the source as 0 and all other nodes as ∞.
• Use a min-priority queue (heap) to store vertices by distance.

2️⃣ Process Nodes:

• Extract the node with the minimum distance.
• Update distances of neighboring nodes if a shorter path is found.

3️⃣ Repeat Until All Nodes Processed:

• Continue picking the next closest node and updating paths.

---

🔹 Python Implementation

import heapq

def dijkstra(graph, start):
    # Number of vertices
    V = len(graph)
    
    # Distance array, initialized to "infinity"
    distances = {node: float('inf') for node in graph}
    distances[start] = 0  # Distance to source is 0
    
    # Priority queue to get the next minimum distance node
    pq = [(0, start)]  # (distance, node)
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)  # Get the closest node
        
        # If found a shorter path before, skip processing
        if current_distance > distances[current_node]:
            continue
        
        # Explore neighbors
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight  # Calculate new distance
            
            if distance < distances[neighbor]:  # Found a shorter path
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))  # Push updated distance
    
    return distances

# Example Graph (Adjacency List)
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

source = 'A'
shortest_paths = dijkstra(graph, source)

# Print shortest distances from source
print("Shortest distances from source:", source)
for node, distance in shortest_paths.items():
    print(f"{node}: {distance}")

---

🔹 Example

Graph Representation:

       A
      / \
     1   4
    /     \
   B --2-- C
    \     /
     5   1
      \ /
       D

Shortest Paths from 'A':

A → A = 0
A → B = 1
A → C = 3  (via B)
A → D = 4  (via C)

---

🔹 Applications of Dijkstra’s Algorithm

✅ Navigation & GPS Systems (Google Maps, Waze)
✅ Network Routing (OSPF routing in computer networks)
✅ AI & Game Development (Pathfinding in games using A*)
✅ Robotics & Automation (Finding shortest paths in warehouse robots)