Και οι δύο βρίσκουν συντομότερες διαδρομές από μια πηγή σε ένα σταθμισμένο γράφημα. Ο 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, καθιστώντας το ένα πλούσιο θέμα σε επίπεδο ανώτατου διευθυντή.