دونوں ایک وزن والے گراف میں ایک ذریعہ سے سب سے مختصر راستے تلاش کرتے ہیں۔ Dijkstra تیز ہے لیکن غیر منفی اوزان کی ضرورت ہے؛ Bellman-Ford سست ہے لیکن منفی کناروں کو سنبھالتا ہے اور منفی سائیکلوں کو شناخت کرتا ہے۔
بار بار سب سے قریب ترین غیر دیکھے گئے نوڈ کو بڑھائیں اور اس کے ہمسایوں کو آرام دیں۔
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
تمام کناروں کو V-1 بار آرام دیں؛ مزید نرمی کا مطلب منفی سائیکل ہے۔
| Dijkstra | Bellman-Ford | |
|---|---|---|
| اوزان | غیر منفی | کوئی بھی (منفی سمیت) |
| وقت | O((V+E) log V) | O(V·E) |
| منفی سائیکل | n/a | شناخت کرتا ہے |
غیر منفی اوزان کے لیے ڈیفالٹ طور پر Dijkstra استعمال کریں (نقشے، نیٹ ورک)۔ جب منفی کنارے موجود ہوں تو Bellman-Ford استعمال کریں (مثال کے طور پر، آربیٹریج)۔ Dijkstra خاموشی سے منفی اوزان پر ٹوٹ جاتا ہے — یہ ایک کلاسک پھندہ ہے۔
سب سے مختصر راستے کے الگورتھم روٹنگ، نیویگیشن، نیٹ ورک پروٹوکول، اور منحصر اخراجات کے تجزیہ میں طاقت فراہم کرتے ہیں۔
Dijkstra پر غیر منفی وزن کی پابندی کو جاننا فیلڈ میں غلط جوابات سے بچاتا ہے۔
نرمی کا خیال حریصانہ اور DP سوچ کو جوڑتا ہے، جو اسے ایک بھرپور سینئر لیول کے موضوع کی طرح بناتا ہے۔