ਦੋਵੇਂ ਇੱਕ ਵਜ਼ਨ ਰਾ ਗ੍ਰਾਫ ਵਿੱਚ ਇੱਕ ਸਰੋਤ ਤੋਂ ਸਭ ਤੋਂ ਛੋਟੇ ਰਸਤੇ ਲੱਭਦੇ ਹਨ। Dijkstra ਤੇਜ਼ ਹੈ ਪਰ ਗੈਰ-ਨਕਾਰਾਤਮਕ ਵਜ਼ਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ; Bellman-Ford ਹੌਲਕਾ ਹੈ ਪਰ ਨਕਾਰਾਤਮਕ ਕਿਨਾਰਿਆਂ ਨੂੰ ਸਭਾਲਦਾ ਹੈ ਅਤੇ ਨਕਾਰਾਤਮਕ ਚੱਕਰਾਂ ਦਾ ਪਤਾ ਲਗਾਉਂਦਾ ਹੈ।
Dijkstra (ਲਾਲਚੀ + min-heap)
ਬਾਰ ਬਾਰ ਸਭ ਤੋਂ ਨਜ਼ਦੀਕੀ ਅਣ-ਵਿਜ਼ਿਟ ਕੀਤਾ ਨੋਡ ਸਤਰ ਕਰੋ ਅਤੇ ਇਸ ਦੇ ਗੁਆਂਢੀਆਂ ਨੂੰ ਢਿੱਲਾ ਕਰੋ।
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
Bellman-Ford (DP-ਅੰਦਾਜ਼ ਰੀਲੈਕਸੇਸ਼ਨ)
ਸਭ ਕਿਨਾਰਿਆਂ ਨੂੰ V-1 ਵਾਰ ਢਿੱਲਾ ਕਰੋ; ਹੋਰ ਰੀਲੈਕਸੇਸ਼ਨ ਮਤਲਬ ਇੱਕ ਨਕਾਰਾਤਮਕ ਚੱਕਰ।
ਤੁਲਨਾ
| Dijkstra | Bellman-Ford | |
|---|---|---|
| ਵਜ਼ਨ | ਗੈਰ-ਨਕਾਰਾਤਮਕ | ਕੋਈ ਵੀ (ਨਕਾਰਾਤਮਕ ਸਮੇਤ) |
| ਸਮਾ | O((V+E) log V) | O(V·E) |
| ਨੈਗ. ਚੱਕਰ | n/a | ਇਸ ਦਾ ਪਤਾ ਲਗਾਉਂਦਾ ਹੈ |
ਕਦੋਂ ਵਰਤਣਾ ਹੈ / ਨੁਕਸਾਨ
ਗੈਰ-ਨਕਾਰਾਤਮਕ ਵਜ਼ਨ ਲਈ ਡਿਫਾਲਟ ਰੂਪ ਵਿੱਚ Dijkstra ਵਰਤੋ (ਨਕਸ਼ਾ, ਨੈੱਟਵਰਕ)। ਜਦੋਂ ਨਕਾਰਾਤਮਕ ਕਿਨਾਰੇ ਮੌਜੂਦ ਹੋਣ (ਮਸਲ, ਆਰਬਿਟ੍ਰੇਜ) ਤਾਂ Bellman-Ford ਵਰਤੋ। Dijkstra ਨਕਾਰਾਤਮਕ ਵਜ਼ਨ ਉੱਤੇ ਚੁੱਪ ਰਿਹਾ ਟੁੱਟਦਾ ਹੈ — ਇੱਕ ਕਲਾਸਿਕ ਫੰਦਾ।
ਇਹ ਮਹੱਤਤਾ ਰੱਖਦਾ ਹੈ
ਸਭ ਤੋਂ ਛੋਟੇ ਰਸਤੇ ਐਲਗੋਰਿਦਮ ਰਾউਟਿੰਗ, ਨੈਵੀਗੇਸ਼ਨ, ਨੈੱਟਵਰਕ ਪ੍ਰੋਟੋਕੋਲ ਅਤੇ ਨਿਰਭਰਤਾ ਲਾਗਤ ਵਿਸ਼ਲੇਸ਼ਣ ਨੂੰ ਸ਼ਕਤੀਸ਼ਾਲੀ ਬਣਾਉਂਦੇ ਹਨ।
Dijkstra ਉੱਤੇ ਗੈਰ-ਨਕਾਰਾਤਮਕ-ਵਜ਼ਨ ਬਾਧਾ ਨੂੰ ਜਾਣਨਾ ਖੇਤਰ ਵਿੱਚ ਗਲਤ ਜਵਾਬਾਂ ਤੋਂ ਬਚਾਉਂਦਾ ਹੈ।
ਰੀਲੈਕਸੇਸ਼ਨ ਵਿਚਾਰ ਲਾਲਚੀ ਅਤੇ DP ਸੋਚ ਨੂੰ ਜੋੜਦਾ ਹੈ, ਇਸ ਨੂੰ ਇੱਕ ਅਮੀਰ ਸੀਨੀਅਰ-ਲਿਵਲ ਵਿਸ਼ਾ ਬਣਾਉਂਦਾ ਹੈ।