બંને એક સ્ત્રોતમાંથી સૌથી ટૂંકો પાથ એક ભારિત ગ્રાફમાં શોધે છે. 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 વિચારને જોડે છે, જે તેને સિનિયર-સ્તરનો સમૃદ્ધ વિષય બનાવે છે.
વિગતવાર જવાબો સાથે IT ઇન્ટરવ્યૂ પ્રશ્નોની લાઇબ્રેરી — જુનિયરથી સિનિયર સુધી.
દાન કરો