Αλγόριθμος του Dijkstra

Ο αλγόριθμος του Dijkstra πήρε το όνομά του από τον Ολλανδό Έντσγκερ Ντάικστρα, ο οποίος τον επινόησε το 1956 και τον δημοσίευσε το 1959. Πρόκειται για έναν αλγόριθμο εύρεσης συντομότερων διαδρομών (single-source shortest path problem) από κοινή αφετηρία σε έναν (κατευθυνόμενο ή μη) γράφο με μη αρνητικά βάρη στις ακμές. Ο αλγόριθμος του Dijkstra είναι άπληστος. Δηλαδή, σε κάθε βήμα επιλέγει την τοπικά βέλτιστη λύση, ώσπου στο τελευταίο βήμα συνθέτει μια συνολικά βέλτιστη λύση. Αν ο γράφος περιέχει αρνητικά βάρη, ο αλγόριθμος του Ντάικστρα δεν δίνει σωστό αποτέλεσμα. Για γράφους που μπορεί να έχουν αρνητικά βάρη στις ακμές, χρησιμοποιούνται πιο περίπλοκοι αλγόριθμοι, όπως αυτός των Bellman και Ford ή των Floyd-Warshall.
Ο αλγόριθμος του Ντάικστρα είναι πλέον ευρέως διαδεδομένος και χρησιμοποιείται σε πολλές εφαρμογές. Χρήση του αλγόριθμου αυτού κάνει το πρωτόκολλο OSPF, το οποίο είναι το εσωτερικό πρωτόκολλο πύλης δικτύου του Διαδικτύου.

Περιγραφή

Έχουμε έναν γράφημα G(V,E), όπου V το σύνολο των κόμβων του και Ε το σύνολο των ακμών του. Επίσης, έχουμε μια συνάρτηση βάρους  ορισμένη στις ακμές του γράφου. Αυτό σημαίνει ότι για να πάμε από έναν κόμβο του γράφου σε έναν άλλο, θα έχουμε κάποιο κόστος. Είναι σημαντικό, όπως θα φανεί παρακάτω, τα βάρη να μην είναι αρνητικά, επειδή διαφορετικά ο αλγόριθμος δεν δίνει σωστό αποτέλεσμα. Ο αλγόριθμος του Ντάικστρα βρίσκει τα μονοπάτια που πρέπει να ακολουθήσουμε από έναν κόμβο-αφετηρία προς τους υπόλοιπους, ώστε να έχουμε το λιγότερο δυνατό κόστος.
Για τη λειτουργία του αλγόριθμου, σε ένα διάνυσμα d[] μεγέθους  αποθηκεύουμε την έως τώρα υπολογισμένη απόσταση των κόμβων από την αφετηρία. Κατά την αρχικοποίηση, οι αποστάσεις σημειώνονται  και  για κάθε , όπου s είναι ο κόμβος-αφετηρία. Επιπλέον ο αλγόριθμος διατηρεί μια ουρά προτεραιότητας Q, για την επεξεργασία των κόμβων του γραφήματος στη σωστή σειρά, και ένα σύνολο S, το σύνολο των κόμβων για τους οποίους ο αλγόριθμος έχει βρει την ελάχιστη διαδρομή. Στην Q εισάγονται όλοι οι κόμβοι του γραφήματος με κλειδί την τιμή d[*], ενώ το σύνολο S είναι αρχικά κενό. Τέλος, ο αλγόριθμος χρησιμοποιεί ένα ακόμη διάνυσμα, το prev[], μεγέθους n, στο οποίο για κάθε κόμβο u αποθηκεύεται ο αμέσως προηγούμενος κόμβος στο ελάχιστο μονοπάτι προς τον u. Για παράδειγμα, έστω ότι το ελάχιστο μονοπάτι από τον s στον b περνά πρώτα από τον a και αμέσως μετά φτάνει στον b. Τότε, prev[b]=a. Αρχικά, κάθε θέση του διανύσματος prev[] λαμβάνει την τιμή null (κενό).

Μετά την αρχικοποίηση των δομών που χρησιμοποιεί, ο αλγόριθμος εξάγει από την Q τον κόμβο x με το ελάχιστο d[*] και τον εισάγει στο σύνολο S. Στο πρώτο βήμα, για παράδειγμα, θα εξάγει τον κόμβο-αφετηρία s, αφού d[s]=0 ενώ όλοι οι υπόλοιποι κόμβοι έχουν άπειρο d[*]. Για κάθε γείτονα y (του x) που δεν ανήκει στο σύνολο S, αν  τότε ενημερώνει το d[y] καταχωρώντας του την τιμή d[x] + w(x,y) και θέτει prev[y]=x. Δηλαδή, αν ο αλγόριθμος υπολογίσει ένα ελαφρύτερο (από το ήδη υπολογισμένο) μονοπάτι για τον κόμβο y, τότε σημειώνει το κόστος του (d[y]) και τον αμέσως προηγούμενο κόμβο του νέου υπολογισμένου μονοπατιού (prev[y]). Με την αλλαγή του d[y] αλλάζει και η θέση του κόμβου y στην ουρά προτεραιότητας Q. Για την ακρίβεια, μεγαλώνει η προτεραιότητα του y, αφού κάθε νέα τιμή του d[y] είναι πάντα μικρότερη από την προηγούμενη. Αφού ο αλγόριθμος εξετάσει όλους τους γείτονες του x που δεν ανήκουν στο σύνολο S, εισάγει στο S τον κόμβο με το ελάχιστο d[*] από όλους όσους δεν ανήκουν στο S. Έπειτα, ο αλγόριθμος επιλέγει πάλι τον πρώτο σε προτεραιότητα κόμβο από την ουρά Q και επαναλαμβάνει τα βήματα αυτά μέχρι να αδειάσει η Q.
Όταν πλέον η Q θα έχει αδειάσει, ο αλγόριθμος θα έχει βρει τα ελάχιστα μονοπάτια από τον κόμβο s προς τους όλους τους υπόλοιπους και τα κόστη τους.
Ο αλγόριθμος είναι άπληστος (greedy): σε κάθε βήμα, εξετάζει μόνο τους γειτονικούς ενός κόμβου (τοπικότητα). Βρίσκει τον κόμβο για τον οποίο έχει υπολογίσει την ελάχιστη διαδρομή και τον εισάγει στο σύνολο S, χρησιμοποιώντας πληροφορίες από προηγούμενα βήματα (σύνθεση). Στο τέλος δίνει ένα αποτέλεσμα για όλους τους κόμβους.

Πολυπλοκότητα

Η χρονική πολυπλοκότητα του αλγόριθμου ποικίλλει ανάλογα με τον γράφο και τις δομές δεδομένων που χρησιμοποιούνται για την υλοποίησή του. Στη γενική περίπτωση, ο αλγόριθμος χρειάζεται χρόνο , όπου V το σύνολο των κόμβων, E το σύνολο των ακμών του γράφου, m ο χρόνος που χρειάζεται για την εξαγωγή του μη-επεξεργασμένου κόμβου με την ελάχιστη ετικέτα απόστασης, δηλαδή την εφαρμογή της εντολής extract_min, και k ο χρόνος που χρειάζεται για την αλλαγή της ετικέτας απόστασης.
Στην πιο απλή περίπτωση όπου οι (μη-επεξεργασμένοι) κόμβοι V\S αποθηκεύονται σε μια λίστα (linked list) ή έναν πίνακα (array), η αναζήτηση του στοιχείου με το μικρότερο κλειδί (ετικέτα απόστασης, d) γίνεται γραμμικά, εξετάζοντας ένα προς ένα όλα τα στοιχεία. Επομένως, η χρονική πολυπλοκότητα του αλγόριθμου είναι . Ο χρόνος αυτός μπορεί να μειωθεί κι άλλο με τη χρήση μιας ουράς προτεραιότητας για την αποθήκευση των κόμβων που είναι μη-επεξεργασμένοι, αυτών δηλαδή που δεν ανήκουν στο σύνολο S που παρουσιάζεται στον ψευδοκώδικα. Ανάλογα με την υλοποίηση της ουράς προτεραιότητας (με σωρό Fibonacci ή δυαδικό σωρό κ.λ.π.), οι χρόνοι για την extract_min και την αλλαγή του κλειδιού ενός στοιχείου ποικίλουν. Για παράδειγμα, στην περίπτωση μιας υλοποίησης ουράς προτεραιότητας με δυαδικό σωρό, η εξαγωγή ελάχιστου στοιχείου (extract_min) και η αλλαγή του κλειδιού ενός στοιχείου παίρνουν χρόνο O(logn), όπου n το πλήθος των στοιχείων του σωρού. Έτσι, η πολυπλοκότητα του αλγόριθμου μειώνεται σε . Για αραιούς γράφους, η πολυπλοκότητα ανάγεται σε .

Κατευθυνόμενα ακυκλικά γραφήματα

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

Απόδειξη ορθότητας

Ο αλγόριθμος του Ντάικστρα είναι άπληστος (greedy), δηλαδή σε κάθε βήμα υπολογίζει την τοπικά βέλτιστη λύση. Στο τέλος, συνθέτει τις τοπικές λύσεις και επιστρέφει μια συνολική. Όμως, το γεγονός ότι οι τοπικές λύσεις είναι βέλτιστες δεν εγγυάται ότι και η σύνθεσή τους θα είναι μια συνολικά βέλτιστη λύση. Γι'αυτό είναι απαραίτητη μια απόδειξη ορθότητας του αλγορίθμου.
Έστω Ρᵥ η διαδρομή που έχει σημειώσει ο αλγόριθμος από τον αρχικό κόμβο s στον κόμβο u. Θα δείξουμε ότι για κάθε κόμβο u του συνόλου S, σε κάθε στάδιο της εκτέλεσης του αλγόριθμου, η Ρᵥ είναι η ελάχιστη διαδρομή. Αυτό μας δείχνει άμεσα ότι ο αλγόριθμος επιστρέφει τη βέλτιστη λύση, αφού στο τελευταίο βήμα το σύνολο S περιέχει όλους τους κόμβους του γραφήματος. Η απόδειξη είναι επαγωγική ως προς το μέγεθος του συνόλου S (των επεξεργασμένων κόμβων).
Για |S|=1, έχουμε ότι S={s} και το κόστος της διαδρομής Ρₛ είναι 0. Αφού δεν υπάρχουν αρνητικά βάρη, αυτή είναι όντως η συντομότερη διαδρομή.
Έστω ότι για |S|=k, με k>1, ο ισχυρισμός ισχύει. Μένει να δείξουμε ότι ο ισχυρισμός ισχύει και για |S|=k+1, έχοντας αυξήσει το σύνολο των επεξεργασμένων κόμβων κατά 1, με την προσθήκη ενός κόμβου, έστω του v. Έστω ότι ο κόμβος u είναι ο αμέσως προηγούμενος του v στη διαδρομή Ρᵥ που έχει σημειώσει ο αλγόριθμος. Λόγω της υπόθεσης της επαγωγής, η διαδρομή  Ρᵤ είναι η συντομότερη από τον αρχικό κόμβο στον u. Θεωρούμε, τώρα, οποιαδήποτε άλλη διαδρομή Πᵥ από τον αρχικό κόμβο στον v. Για να αποδείξουμε την πρόταση, αρκεί να δείξουμε ότι η Πᵥ έχει ίσο ή μεγαλύτερο κόστος από αυτό της Ρᵥ.
Η οι κόμβοι της διαδρομής Πᵥ από ένα σημείο και μετά δεν ανήκουν στο σύνολο S. Υποθέτουμε ότι ο y είναι ο πρώτος κόμβος της Πᵥ που δεν ανήκει στο S και ότι ο αμέσως προηγούμενός του (που ανήκει στο S) είναι ο x. Κατά την επανάληψη k+1 του αλγόριθμου, εξετάζονται όλες οι διαδρομές από τον αρχικό κόμβο προς τους κόμβους που είναι γειτονικοί του S, δηλαδή εξετάζονται και η Ρᵥ και η Πy, αλλά υπολογίζοντας τα αντίστοιχα μήκη των διαδρομών και συκγρίνωντάς τα, προτιμάται η Ρᵥ και τελικά στο σύνολο S προστίθεται ο κόμβος v. Αυτό σημαίνει ότι το μήκος της Ρᵥ είναι ίσο ή μικρότερο από το μήκος της Πy. Και αφού η Πy είναι ένα μόνο μέρος της διαδρομής Πᵥ και δεν υπάρχουν αρνητικά βάρη, είναι προφανές ότι το μήκος της Πᵥ θα είναι κι αυτό ίσο ή μεγαλύτερο από το μήκος της Ρᵥ.
Καθώς αυτό ισχύει για ολες τις πιθανές διαδρομές Πᵥ, έχουμε δείξει ότι η  Ρᵥ είναι η βέλτιστη.

Αρνητικά βάρη ακμών

Όπως έχει ήδη ίσως καταστεί εμφανές, ο αλγόριθμος του Ντάικστρα δεν λειτουργεί σωστά, αν κάποιες ακμές του γράφου έχουν αρνητικά βάρη. Σε έναν τέτοιο γράφο δεν εξασφαλίζεται ότι η λύση που δίνει ο αλγόριθμος είναι η βέλτιστη. Αυτό συμβαίνει λόγω της σημείωσης επεξεργασμένο που λαμβάνουν όλοι οι κόμβοι για τους οποίους έχει υπολογιστεί η συντομότερη διαδρομή από τον αρχικό κόμβο. Οι επεξεργασμένοι κόμβοι (αυτοί που ανήκουν στο σύνολο S) δεν εξετάζονται ξανά από τον αλγόριθμο. Έτσι, μια πιθανώς συντομότερη διαδρομή που θα μπορούσε να προκύψει (για έναν επεξεργασμένο κόμβο) μέσω μιας ακμής αρνητικού βάρους, δεν λαμβάνεται υπόψη.
Αν όμως αφαιρεθεί αυτή η λειτουργία (της σημείωσης των κόμβων ως επεξεργασμένων), ο αλγόριθμος μπορεί να μπει σε έναν ατέρμονα βρόχο (endless loop) επανεξετάζοντας συνεχώς κάποιους κόμβους και μειώνοντας την ετικέτα απόστασής τους. Αυτό θα συμβεί στην περίπτωση που ο γράφος περιέχει αρνητικό κύκλο, δηλαδή μια διαδρομή από έναν κόμβο προς τον ίδιο, της οποίας το συνολικό βάρος είναι αρνητικό. Ο αλγόριθμος θα εξετάζει συνεχώς τους κόμβους του κύκλου, μειώνοντας τις ετικέτες απόστασής τους όλο και περισσότερο και δεν θα σταματήσει ποτέ. Ουσιαστικά, σε έναν γράφο που περιέχει κύκλο αρνητικού βάρους, δεν υπάρχει συντομότερη διαδρομή, αφού περνώντας από τον κύκλο αυτό θα έχουμε πάντα μια ακόμη συντομότερη διαδρομή. Αλλά ούτε αυτή θα είναι η συντομότερη, αφού ξαναπερνώντας από τον κύκλο θα βρούμε μια ακόμη συντομότερη διαδρομή κ.ο.κ.
Ένας αλγόριθμος που αντιμετωπίζει το πρόβλημα της εύρεσης συντομότερης διαδρομής από κοινή αφετηρία (single-source shortest path problem) σε γραφήματα που μπορεί να έχουν και αρνητικά βάρη είναι ο αλγόριθμος Bellman-Ford, ο οποίος μάλιστα στην περίπτωση που το γράφημα έχει αρνητικό κύκλο, τον εντοπίζει και τερματίζει χωρίς να δώσει κάποια λύση. Ένας ακόμη αλγόριθμος για το ίδιο πρόβλημα, χωρίς τον περιορισμό των μη αρνητικών βαρών, είναι αυτός των Floyd και Warshall, ο οποίος όμως δεν μπορεί να εντοπίσει αρνητικούς κύκλους και μπορεί να μπει σε ατέρμονα βρόχο, επομένως η χρήση του θέλει προσοχή.