Ο αλγόριθμος του Dijkstra βήμα-βήμα με παράδειγμα και κώδικα Python

Ας δούμε ένα παράδειγμα βήμα προς βήμα για να καταλάβετε ακριβώς πώς λειτουργεί ο αλγόριθμος.

Έστω ότι έχουμε 4 πόλεις (κόμβους): Α, Β, Γ, Δ. Θέλουμε να βρούμε τις συντομότερες αποστάσεις ξεκινώντας από την πόλη Α.
Οι δρόμοι (ακμές) μεταξύ τους έχουν τα εξής βάρη (αποστάσεις σε χιλιόμετρα):

Από Α προς Β: 4 χλμ.
Από Α προς Γ: 2 χλμ.
Από Γ προς Β: 1 χλμ.
Από Β προς Δ: 5 χλμ.
Από Γ προς Δ: 8 χλμ.

📍 Αρχική Κατάσταση

Φτιάχνουμε έναν πίνακα με τις αποστάσεις από το Α και βάζουμε παντού άπειρο, εκτός από το Α που είναι 0.

Α: 0
Β: ∞
Γ: ∞
Δ: ∞
Μη επισκεπτόμενοι κόμβοι: {Α, Β, Γ, Δ}

🔁 Βήμα 1: Επιλογή του Α (Απόσταση = 0)

Επιλέγουμε το Α γιατί έχει τη μικρότερη απόσταση. Κοιτάμε τους γείτονές του (Β και Γ) και κάνουμε χαλάρωση (update):

Για το Β: Η νέα απόσταση είναι 0 + 4 = 4. Επειδή το 4 είναι μικρότερο από το ∞, το αποθηκεύουμε.
Για το Γ: Η νέα απόσταση είναι 0 + 2 = 2. Επειδή το 2 είναι μικρότερο από το ∞, το αποθηκεύουμε.

Μαρκάρουμε το Α ως επισκεπτόμενο.

Τρέχουσες αποστάσεις: Α: 0, Β: 4, Γ: 2, Δ: ∞
Μη επισκεπτόμενοι κόμβοι: {Β, Γ, Δ}

🔁 Βήμα 2: Επιλογή του Γ (Απόσταση = 2)

Από τους εναπομείναντες {Β, Γ, Δ}, η μικρότερη απόσταση είναι του Γ (2). Εξετάζουμε τους μη επισκεπτόμενους γείτονές του (Β και Δ):

Για το Β: Μέσω του Γ, η απόσταση είναι Απόσταση(Γ) + Γ-Β = 2 + 1 = 3. Η παλιά απόσταση για το Β ήταν 4. Επειδή το 3 είναι μικρότερο από το 4, την ενημερώνουμε σε 3! (Βρήκαμε συντομότερο δρόμο για το Β μέσω του Γ).
Για το Δ: Μέσω του Γ, η απόσταση είναι 2 + 8 = 10. Επειδή το 10 είναι μικρότερο από το ∞, το αποθηκεύουμε.

Μαρκάρουμε το Γ ως επισκεπτόμενο.

Τρέχουσες αποστάσεις: Α: 0, Γ: 2, Β: 3, Δ: 10
Μη επισκεπτόμενοι κόμβοι: {Β, Δ}

🔁 Βήμα 3: Επιλογή του Β (Απόσταση = 3)

Από τους {Β, Δ}, μικρότερη απόσταση έχει το Β (3). Εξετάζουμε τον μη επισκεπτόμενο γείτονά του (Δ):

Για το Δ: Μέσω του Β, η απόσταση είναι Απόσταση(Β) + Β-Δ = 3 + 5 = 8. Η παλιά απόσταση για το Δ ήταν 10. Επειδή το 8 είναι μικρότερο από το 10, την ενημερώνουμε σε 8.

Μαρκάρουμε το Β ως επισκεπτόμενο.

Τρέχουσες αποστάσεις: Α: 0, Γ: 2, Β: 3, Δ: 8
Μη επισκεπτόμενοι κόμβοι: {Δ}

🔁 Βήμα 4: Επιλογή του Δ (Απόσταση = 8)

Απομένει μόνο το Δ. Δεν έχει άλλους μη επισκεπτόμενους γείτονες να ελέγξει. Μαρκάρεται ως επισκεπτόμενο.

🏆 Τελικό Αποτέλεσμα

Ο αλγόριθμος ολοκληρώθηκε! Οι συντομότερες αποστάσεις από το Α είναι:

Προς Α: 0
Προς Γ: 2
Προς Β: 3 (μέσω του Γ)
Προς Δ: 8 (μέσω του Γ και μετά του Β)

💻 Κώδικας σε Python

Αν θέλετε να δείτε πώς μεταφράζεται αυτό σε κώδικα, ορίστε μια απλή υλοποίηση με τη χρήση της βιβλιοθήκης heapq (ουρά προτεραιότητας):

import heapq

def dijkstra(graph, start):
    # Αρχικοποίηση αποστάσεων με άπειρο
    distances = {node: float('infinity') 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].items():
            distance = current_distance + weight
            
            # Αν βρέθηκε συντομότερο μονοπάτι
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
                
    return distances

# Ορισμός του γραφήματος από το παράδειγμά μας
my_graph = {
    'A': {'B': 4, 'Γ': 2},
    'B': {'Δ': 5},
    'Γ': {'B': 1, 'Δ': 8},
    'Δ': {}
}

# Εκτέλεση
print(dijkstra(my_graph, 'A'))
# Έξοδος: {'A': 0, 'B': 3, 'Γ': 2, 'Δ': 8}