Dijkstra
ডাইকস্ট্রা
Non-negative weight-এর graph-এ single-source shortest path বের করা greedy algorithm — priority queue থেকে সবচেয়ে কাছের node নিয়ে edge relax করে।
also: dijkstra algorithm, dijkstra's algorithm
মূল লুপ:
while pq:
d, u = heappop(pq)
if d > dist[u]: continue # stale entry
for v, w in adj[u]:
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd
heappush(pq, (nd, v))Binary heap-এ O((V+E) log V); Fibonacci heap-এ decrease-key cheap হলে O(E + V log V)।
কেন non-negative লাগে: greedy assumption — node pop করার মুহূর্তে তার distance final; negative edge পরে সেটা ভেঙে দিতে পারে। Negative edge থাকলে Bellman-Ford।
Unweighted graph-এ Dijkstra BFS-এ নেমে আসে। GPS navigation, OSPF routing — practical জীবন বিশাল।