# Dijkstra's Algorithm — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/dijkstra

> Finds shortest paths from one source to all nodes in a weighted graph with non-negative edges.

## Greedy on a min-heap

Dijkstra keeps a `dist[]` array initialized to infinity except the source (0), and always expands the **closest unvisited node** next using a **min-heap**. Once a node is popped with its final distance, it's never revisited — this greedy choice is safe because all edge weights are **non-negative**.

## Implementation

Push `(distance, node)` tuples; the heap always surfaces the smallest distance first. Skip stale entries where a shorter path was already found.

```python
import heapq

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

Output:

```
# g[u] = list of (neighbour, weight)
dijkstra(5, g, 0)  # -> shortest distance from node 0 to all others
```

## Complexity & limits

With a binary heap: `O((V+E) log V)`. Dijkstra **fails with negative edge weights** — a later cheaper path can undercut an already-finalized distance. Use Bellman-Ford when negatives are possible.

## Quick check

Test the key constraint.

**Quiz:** Dijkstra's algorithm gives correct results only when:

- [ ] The graph is undirected
- [x] All edge weights are non-negative
- [ ] The graph has no cycles
- [ ] The graph is a tree

*Answer:* All edge weights are non-negative. Negative weights can invalidate the greedy 'closest node is final' assumption — use Bellman-Ford instead.