# Dijkstra's Algorithm — डेटा स्ट्रक्चर और एल्गोरिदम

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

> एक weighted graph में गैर-ऋणात्मक edges के साथ, एक source से सभी nodes तक सबसे छोटे रास्ते खोजता है।

## Min-heap पर Greedy

Dijkstra एक `dist[]` array रखता है जो source (0) को छोड़कर infinity पर initialize होता है, और हमेशा अगले में **सबसे नज़दीकी unvisited node** को एक **min-heap** से expand करता है। एक बार कोई node उसकी final distance के साथ pop हो जाए, तो वह फिर नहीं देखा जाता — यह greedy चुनाव सुरक्षित है क्योंकि सभी edge weights **गैर-ऋणात्मक** हैं।

## क्रियान्वयन

`(distance, node)` tuples push करें; heap हमेशा सबसे छोटी distance पहले देता है। पुराने entries छोड़ें जहाँ पहले ही छोटा रास्ता मिल चुका हो।

```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 और सीमाएँ

Binary heap के साथ: `O((V+E) log V)`। Dijkstra **negative edge weights के साथ विफल** होता है — बाद का सस्ता रास्ता पहले से finalize हुई distance को कमज़ोर कर सकता है। जब negatives संभव हों तो Bellman-Ford इस्तेमाल करें।

## त्वरित जांच

मुख्य शर्त परखें।

**Quiz:** Dijkstra's algorithm सही परिणाम केवल तब देता है जब:

- [ ] Graph undirected हो
- [x] सभी edge weights गैर-ऋणात्मक हों
- [ ] Graph में कोई cycle न हो
- [ ] Graph एक tree हो

*Answer:* सभी edge weights गैर-ऋणात्मक हों. Negative weights greedy 'सबसे नज़दीकी node final है' मान्यता को गलत कर सकते हैं — इसकी जगह Bellman-Ford इस्तेमाल करें।