दोनों एक भारित ग्राफ में एक स्रोत से सबसे छोटे पथ खोजते हैं। 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 सोच को जोड़ता है, जिससे यह एक समृद्ध वरिष्ठ-स्तरीय विषय बन जाता है।