రెండూ బరువున్న గ్రాఫ్లో మూలం నుండి సంక్షిప్త మార్గాలను కనుగొంటాయి. 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 ఆలోచనను అనుసంధానిస్తుంది, ఇది చిన్నపాటి-స్థర విషయం చేస్తుంది.