दुबै एक भारित ग्राफमा स्रोतबाट सबैभन्दा छोटो पथ खोज्छन्। 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) |
| नकारात्मक चक्र | लागू छैन | पत्ता लगाउँछ |
नकारात्मक रहित वजनको लागि Dijkstra पूर्वनिर्धारितको रूपमा प्रयोग गर्नुहोस् (नक्सा, नेटवर्क)। नकारात्मक किनारहरू अवस्थित हुँदा Bellman-Ford प्रयोग गर्नुहोस् (उदाहरण, आर्बिट्राज)। Dijkstra नकारात्मक वजनमा चुपचाप टुट्छ — एक शास्त्रीय फन्दा।
सबैभन्दा छोटो पथ एल्गोरिदमहरूले रूटिङ, नेविगेशन, नेटवर्क प्रोटोकल, र निर्भरता लागत विश्लेषण शक्तिशाली गर्छन्।
Dijkstrामा नकारात्मक-वजन-बाधा जानुहोस् क्षेत्रमा गलत उत्तरहरू रोक्छ।
शिथिलता विचारले लोभी र DP सोच जोड्छ, यसलाई एक समृद्ध वरिष्ठ-स्तरको विषय बनाउँछ।