Dijkstra's Algorithm

Dijkstra’s algorithm is a classic graph traversal method used to find the shortest path from a source node to all other nodes in a weighted graph. It guarantees the shortest path for graphs with non-negative edge weights.

---

Steps of the Algorithm

1. Initialization:
   • Assign a tentative distance of 0 to the source node and infinity (∞) to all others.
   • Use a priority queue (min-heap) to track nodes to visit, prioritized by their tentative distance.
2. Processing Nodes:
   • While there are unvisited nodes:
     • Extract the node with the smallest tentative distance from the queue.
     • Update the distances to its neighbors if a shorter path is found through this node.
3. Termination:
   • The algorithm stops when all nodes are visited, or the shortest path to the desired destination is found.

Code Implementation in Python

import heapq
 
def dijkstra(graph, source):
    # Priority queue to keep track of (distance, node)
    priority_queue = []
    heapq.heappush(priority_queue, (0, source))
 
    # Distance dictionary to store shortest distances
    distances = {node: float('inf') for node in graph}
    distances[source] = 0
 
    # Set of visited nodes
    visited = set()
 
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
 
        if current_node in visited:
            continue
        visited.add(current_node)
 
        # Process neighbors
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
 
    return distances

---

Example Usage

Given the following graph:

    A ---1--- B
    |        / |
    4      2   6
    |    /     |
    C ---3-----D

Graph Representation:

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 6},
    'C': {'A': 4, 'B': 2, 'D': 3},
    'D': {'B': 6, 'C': 3}
}

Running the Algorithm:

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

Output:

{'A': 0, 'B': 1, 'C': 3, 'D': 6}

Explanation:

• A → B: Cost = 1
• A → C: Cost = 3 (via B)
• A → D: Cost = 6 (via C)

---

Complexity Analysis

• Time Complexity:
  • Using Min-Heap: (O((V + E) \log V)), where (V) is the number of vertices and (E) is the number of edges.
• Space Complexity:
  • (O(V + E)) for storing the graph and distances.

---