Dijkstra's Algorithm

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 छोड़ें जहाँ पहले ही छोटा रास्ता मिल चुका हो।

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 इस्तेमाल करें।

त्वरित जांच

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

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

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