Zyora-EDU-32B

Explain Dijkstra's algorithm with time complexity analysis

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

**Algorithm:**
1. Initialize dist[source] = 0, all others = ∞
2. Use a min-priority queue
3. Extract vertex u with minimum distance
4. For each neighbor v: relax edge (u, v)

**Time Complexity:**
• With binary heap: O((V + E) log V)
• With Fibonacci heap: O(E + V log V)
• With adjacency matrix: O(V²)

Now write it in Python with a min-heap

```python
import heapq

def dijkstra(graph, src):
    dist = {v: float('inf') for v in graph}
    dist[src] = 0
    pq = [(0, src)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist
```