Αλγόριθμος του Dijkstra στην Python: Οδηγός για τη Συντομότερη Διαδρομή

Τι είναι ο Αλγόριθμος του Dijkstra;

Ο αλγόριθμος του Dijkstra είναι ένας από τους πιο γνωστούς και χρήσιμους αλγορίθμους για την εύρεση της συντομότερης διαδρομής μεταξύ δύο κόμβων σε ένα γράφημα. Χρησιμοποιείται σε πλήθος εφαρμογών, από την πλοήγηση GPS μέχρι τη δρομολόγηση σε δίκτυα υπολογιστών.

---

Πώς δουλεύει ο αλγόριθμος;

Έχουμε ένα γράφημα, δηλαδή μια συλλογή κόμβων που συνδέονται μεταξύ τους με ακμές, κάθε μία από τις οποίες έχει ένα βάρος (π.χ. απόσταση, κόστος ή χρόνο). 

Ο αλγόριθμος ξεκινά από έναν κόμβο εκκίνησης και «εξερευνά» όλους τους δυνατούς δρόμους, ενημερώνοντας τις μικρότερες αποστάσεις που βρίσκει, μέχρι να βρει τη συντομότερη διαδρομή προς όλους τους υπόλοιπους κόμβους.

---

Υλοποίηση του αλγορίθμου στην Python

Παρακάτω παρουσιάζουμε μια απλή και κατανοητή υλοποίηση με τη χρήση προτεραιοποιημένης ουράς (heap) για αποδοτικότητα.

python
import heapq
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances
# Παράδειγμα γράφου και κλήση του αλγορίθμου
graph = {
    'A': [('B', 5), ('C', 1)],
    'B': [('A', 5), ('C', 2), ('D', 1)],
    'C': [('A', 1), ('B', 2), ('D', 4), ('E', 8)],
    'D': [('B', 1), ('C', 4), ('E', 3), ('F', 6)],
    'E': [('C', 8), ('D', 3)],
    'F': [('D', 6)]
}
distances = dijkstra(graph, 'A')
print(distances)

---

Τι βλέπουμε;

Η έξοδος του παραπάνω κώδικα μας δείχνει την ελάχιστη απόσταση από τον κόμβο 'A' σε όλους τους υπόλοιπους κόμβους.

---

Συμπεράσματα

Ο αλγόριθμος του Dijkstra είναι το θεμέλιο πολλών σύγχρονων τεχνολογιών που απαιτούν γρήγορη και αποτελεσματική εύρεση διαδρομών. Με λίγα βασικά βήματα και λίγες γραμμές κώδικα, μπορούμε να υλοποιήσουμε έναν αλγόριθμο που κάνει ακριβώς αυτό.