Dijkstra’s Algorithm (Python implementation)

Dijkstra’s Algorithm is a fundamental graph algorithm used to find the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. It is widely applied in network routing, GPS navigation systems, and optimization problems.

---

🌍 How Dijkstra’s Algorithm Works

1. Initialization: Set the source node’s distance to 0 and all others to infinity.
2. Selection: Pick the unvisited node with the smallest known distance.
3. Relaxation: Update distances to neighboring nodes if a shorter path is found.
4. Repeat: Continue until all nodes are visited or shortest paths are determined.

Time complexity depends on the data structure used:

• With a simple array: O(V²)
• With a priority queue (min-heap): O((V + E) log V)

---

🐍 Python Implementation

import heapq

def dijkstra(graph, src):
    V = len(graph)
    dist = [float('inf')] * V
    dist[src] = 0

    pq = [(0, src)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))

    print("Vertex   Distance from Source")
    for i in range(V):
        print(i, "\t\t", dist[i])

# Example usage
graph = [
    [(1, 10), (4, 5)],   # edges from node 0
    [(2, 1)],            # edges from node 1
    [(3, 4)],            # edges from node 2
    [(0, 7), (2, 6)],    # edges from node 3
    [(1, 3), (2, 9)]     # edges from node 4
]

dijkstra(graph, 0)

---

✨ Example Output

Vertex   Distance from Source
0         0
1         8
2         9
3         13
4         5

This shows the shortest distance from the source node 0 to all other nodes.

---

📖 Conclusion

Dijkstra’s Algorithm is a cornerstone of graph theory, enabling efficient shortest-path calculations in weighted graphs. The Python implementation using heapq makes it concise and efficient, suitable for practical applications like routing systems and network optimization.