दोन्ही स्रोतापासून सर्वात लहान मार्ग भारित आलेखामध्ये शोधतात। 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 वर नॉन-नेगेटिव्ह-वजन प्रतिबंध जाणून घेतल्याने क्षेत्रातील चुकीच्या उत्तरांपासून बचाव होतो।
शिथिलकरण विचार greedy आणि DP विचार जोडतो, ज्यामुळे हे एक समृद्ध सिनियर-स्तरीय विषय बनतो.