Αλγόριθμος του Dijkstra — Συντομότερη διαδρομή βήμα βήμα

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

Η βασική ιδέα είναι άπληστη: συνεχίζεις πάντα από τον μη οριστικοποιημένο κόμβο με τη μικρότερη γνωστή απόσταση. Αυτό λειτουργεί μόνο με την προϋπόθεση των μη αρνητικών βαρών.

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

Χρησιμοποίησε τον αλγόριθμο του Dijkstra όταν έχεις έναν γράφο με κόστη στις ακμές και θέλεις τη φθηνότερη διαδρομή. Το κόστος μπορεί να παριστάνει απόσταση, χρόνο μετακίνησης, ενέργεια ή κάποια άλλη ποσότητα που θέλεις να ελαχιστοποιήσεις.

Λειτουργεί σε κατευθυνόμενους ή μη κατευθυνόμενους γράφους. Η βασική προϋπόθεση είναι σαφής: κάθε βάρος ακμής πρέπει να είναι τουλάχιστον $0$.

Πώς λειτουργεί ο αλγόριθμος

Κάθε κόμβος διατηρεί μια προσωρινή απόσταση από τον αρχικό κόμβο. Στην αρχή, ο αρχικός κόμβος έχει απόσταση $0$ και κάθε άλλος κόμβος έχει απόσταση $\infty$.

Έπειτα επαναλαμβάνεις τον εξής βρόχο:

1. Επίλεξε τον μη οριστικοποιημένο κόμβο με τη μικρότερη προσωρινή απόσταση.
2. Έλεγξε κάθε γειτονικό κόμβο μέσω αυτού του κόμβου.
3. Αν η νέα διαδρομή είναι φθηνότερη, ενημέρωσε την απόσταση του γειτονικού κόμβου.
4. Σημείωσε τον τρέχοντα κόμβο ως οριστικοποιημένο.

Το βήμα 3 λέγεται χαλάρωση. Ένας οριστικοποιημένος κόμβος έχει ολοκληρωθεί: η συντομότερη απόστασή του είναι τελική, αρκεί ο γράφος να μην έχει αρνητικά βάρη ακμών.

Ο αλγόριθμος του Dijkstra βήμα βήμα

Εδώ είναι η πλήρης διαδικασία σε σύντομη μορφή:

1. Διάλεξε έναν αρχικό κόμβο.
2. Θέσε την απόστασή του σε $0$ και κάθε άλλη απόσταση σε $\infty$.
3. Επίλεξε τον μη οριστικοποιημένο κόμβο με τη μικρότερη προσωρινή απόσταση.
4. Χαλάρωσε τις εξερχόμενες ακμές του.
5. Σημείωσε αυτόν τον κόμβο ως οριστικοποιημένο.
6. Επανάλαβε μέχρι να οριστικοποιηθούν όλοι οι προσβάσιμοι κόμβοι ή σταμάτησε μόλις οριστικοποιηθεί ο κόμβος-στόχος.

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

Παράδειγμα συντομότερης διαδρομής

Ας υποθέσουμε ότι ο γράφος έχει τα εξής βάρη ακμών:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Θέλουμε τη συντομότερη διαδρομή από το $A$ στο $D$.

Ξεκινάμε με:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Οριστικοποιούμε πρώτα το $A$ και χαλαρώνουμε τις ακμές του:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

Η μικρότερη μη οριστικοποιημένη απόσταση είναι τώρα στο $C$, οπότε οριστικοποιούμε στη συνέχεια το $C$.

Περνώντας μέσω του $C$:

• Μέσω του $C$, η διαδρομή προς το $B$ κοστίζει $1+2=3$, που είναι καλύτερο από το $4$, οπότε ενημερώνουμε $\text{dist}(B)=3$.
• Μέσω του $C$, η διαδρομή προς το $D$ κοστίζει $1+5=6$, οπότε θέτουμε $\text{dist}(D)=6$.

Τώρα το $B$ έχει τη μικρότερη μη οριστικοποιημένη απόσταση, οπότε οριστικοποιούμε το $B$.

Περνώντας μέσω του $B$, η διαδρομή προς το $D$ κοστίζει:

$$3+1=4$$

Αυτό βελτιώνει το $6$, οπότε ενημερώνουμε το $\text{dist}(D)$ από $6$ σε $4$.

Τώρα το $D$ είναι ο μη οριστικοποιημένος κόμβος με τη μικρότερη απόσταση. Το οριστικοποιούμε και σταματάμε.

Η συντομότερη διαδρομή είναι:

$$A \to C \to B \to D$$

με συνολικό κόστος:

$$1+2+1=4$$

Αυτό το παράδειγμα δείχνει το βασικό μοτίβο: μια διαδρομή που αρχικά φαινόταν χειρότερη, η $A \to B$, έγινε αργότερα καλύτερη μέσω του $C$. Ο αλγόριθμος του Dijkstra το επιτρέπει αυτό όσο το $B$ παραμένει μη οριστικοποιημένο. Μόλις ένας κόμβος οριστικοποιηθεί, η απόστασή του δεν θα αλλάξει.

Γιατί έχουν σημασία τα μη αρνητικά βάρη

Ας υποθέσουμε ότι ο τρέχων φθηνότερος μη οριστικοποιημένος κόμβος έχει απόσταση $d$. Οποιαδήποτε νέα διαδρομή προς αυτόν τον κόμβο που θα βρεθεί αργότερα θα πρέπει να προέρχεται από άλλον μη οριστικοποιημένο κόμβο με προσωρινή απόσταση τουλάχιστον $d$, και έπειτα να προσθέτει μια ακμή με βάρος τουλάχιστον $0$.

Άρα αυτή η μεταγενέστερη διαδρομή δεν μπορεί να είναι καλύτερη από το $d$. Γι’ αυτό η οριστικοποίηση της μικρότερης προσωρινής απόστασης είναι ασφαλής όταν όλα τα βάρη είναι μη αρνητικά.

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

Συνηθισμένα λάθη με τον αλγόριθμο του Dijkstra

Χρήση του με αρνητική ακμή

Ακόμα και μία αρνητική ακμή μπορεί να καταστρέψει την άπληστη λογική. Αν είναι πιθανά αρνητικά βάρη, χρησιμοποίησε άλλη μέθοδο για συντομότερες διαδρομές.

Να θεωρείς ότι το "seen" σημαίνει "finished"

Ένας κόμβος μπορεί ήδη να έχει προσωρινή απόσταση και παρ’ όλα αυτά να μην έχει ολοκληρωθεί. Μόνο ένας οριστικοποιημένος κόμβος έχει τελική συντομότερη απόσταση.

Να ξεχνάς τον πίνακα προηγούμενων κόμβων

Οι αποστάσεις σου δίνουν το κόστος. Αν θέλεις και την ίδια τη διαδρομή, αποθήκευσε ποιος κόμβος βελτίωσε τελευταίος κάθε απόσταση.

Πού χρησιμοποιείται ο αλγόριθμος του Dijkstra

Ο αλγόριθμος του Dijkstra χρησιμοποιείται όταν ένα πρόβλημα μπορεί να μοντελοποιηθεί ως κίνηση μέσα σε γράφο με μη αρνητικά κόστη:

• Σχεδιασμός διαδρομών σε χάρτες
• Δρομολόγηση δικτύων
• Κίνηση ρομπότ σε σταθμισμένα πλέγματα
• Εύρεση διαδρομής σε παιχνίδια όταν τα κόστη κίνησης διαφέρουν

Είναι επίσης ένα κλασικό παράδειγμα άπληστου αλγορίθμου, του οποίου η ορθότητα εξαρτάται από μια ακριβή προϋπόθεση.

Δοκίμασε ένα παρόμοιο πρόβλημα

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