Αλγόριθμος του Ντάικστρα

Ο αλγόριθμος του Ντάικστρα πήρε το όνομά του από τον Ολλανδό Έντσγκερ Ντάικστρα, ο οποίος τον επινόησε το 1956 και τον δημοσίευσε το 1959. Πρόκειται για έναν αλγόριθμο εύρεσης συντομότερων διαδρομών (single-source shortest path problem) από κοινή αφετηρία σε έναν (κατευθυνόμενο ή μη) γράφο με μη αρνητικά βάρη στις ακμές. Ο αλγόριθμος του Ντάικστρα είναι άπληστος. Δηλαδή, σε κάθε βήμα επιλέγει την τοπικά βέλτιστη λύση, ώσπου στο τελευταίο βήμα συνθέτει μια συνολικά βέλτιστη λύση^[1]. Αν ο γράφος περιέχει αρνητικά βάρη, ο αλγόριθμος του Ντάικστρα δεν δίνει σωστό αποτέλεσμα. Για γράφους που μπορεί να έχουν αρνητικά βάρη στις ακμές, χρησιμοποιούνται πιο περίπλοκοι αλγόριθμοι, όπως αυτός των Μπέλμαν και Φορντ ή των Φλόιντ-Ουόρσολ.

Ο αλγόριθμος του Ντάικστρα είναι πλέον ευρέως διαδεδομένος και χρησιμοποιείται σε πολλές εφαρμογές. Χρήση του αλγόριθμου αυτού κάνει το πρωτόκολλο OSPF, το οποίο είναι το εσωτερικό πρωτόκολλο πύλης δικτύου του Διαδικτύου.

Περιγραφή

Έχουμε έναν γράφημα G(V,E), όπου V το σύνολο των κόμβων του και Ε το σύνολο των ακμών του. Επίσης, έχουμε μια συνάρτηση βάρους ${\displaystyle w:E\to \mathbb {R} ^{+}\cup \{0\}}$ ορισμένη στις ακμές του γράφου. Αυτό σημαίνει ότι για να πάμε από έναν κόμβο του γράφου σε έναν άλλο, θα έχουμε κάποιο κόστος. Είναι σημαντικό, όπως θα φανεί παρακάτω, τα βάρη να μην είναι αρνητικά, επειδή διαφορετικά ο αλγόριθμος δεν δίνει σωστό αποτέλεσμα. Ο αλγόριθμος του Ντάικστρα βρίσκει τα μονοπάτια που πρέπει να ακολουθήσουμε από έναν κόμβο-αφετηρία προς τους υπόλοιπους, ώστε να έχουμε το λιγότερο δυνατό κόστος.

Για τη λειτουργία του αλγόριθμου, σε ένα διάνυσμα d[] μεγέθους ${\displaystyle |V|=n}$ αποθηκεύουμε την έως τώρα υπολογισμένη απόσταση των κόμβων από την αφετηρία. Κατά την αρχικοποίηση, οι αποστάσεις σημειώνονται ${\displaystyle d[s]=0}$ και ${\displaystyle d[v]=+\infty }$ για κάθε ${\displaystyle v\not =s}$, όπου 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, αν ${\displaystyle d[y]>d[x]+w(x,y)}$ τότε ενημερώνει το 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.

Χρήση του αλγόριθμου του Ντάικστρα για να βρεθεί η συντομότερη διαδρομή μεταξύ a και b: 1ο βήμα: Ξεκινώντας από το a, συγκρίνει ποια είναι η πιο 'ελαφριά' διαδρομή (εδώ προς τον κόμβο 2) τοποθετώντας 'βάρη' δίπλα σε αυτές που συγκρίνει (π.χ. για τον κόμβο 3 έβαλε το 'βάρος' 9). 2ο βήμα: Από τον κόμβο 2 (που επέλεξε πριν λόγω της σύγκρισης) κάνει το ίδιο με το βήμα 1, προσθέτει τα συνολικά 'βάρη' απ' τα οποία πέρασε αλλά και συγκρίνει τα 'βάρη' που τοποθέτησε πριν: Δηλαδή συγκρίνει τις διαδρομές 1-2-3 ('βάρος': 10 + 7 = 17) και 1-2-4 ('βάρος' 15 + 7 = 22). Έπειτα συγκρίνει την 1-2-3 με την 1-3 στην οποία έβαλε στο βήμα 1 το 'βάρος' 9 και βλέπει ότι 9 < 10 +7. Οπότε η συμφέρουσα διαδρομή είναι η 1-3 και όχι η 1-2-3. Επομένως δεν 'πατά' στον κόμβο 2 (ωστόσο τον αποκλείει με κόκκινο για να μην τον ξαναψάξει). 3ο βήμα: Από τον 3 που βρισκόμαστε ξαναγίνεται η διαδικασία. Συγκρίνει την 1-3-6 (βάρος 9+2=11) και την 1-3-4 (βάρος 9+11=20). Προφανώς επιλέγει την 1-3-6 αφού 11<20. Έπειτα συγκρίνει την 1-3-6 με την 1-6 και επιλέγει την πρώτη γιατί έχουν βάρη 11 και 14 αντίστοιχα. 4ο βήμα: Η μόνη επιλογή πλέον είναι ο προορισμός b. Επομένως η συντομότερη διαδρομή είναι η 1-3-6-5 με βάρος 20.

Όταν πλέον η Q θα έχει αδειάσει, ο αλγόριθμος θα έχει βρει τα ελάχιστα μονοπάτια από τον κόμβο s προς τους όλους τους υπόλοιπους και τα κόστη τους.

Ο αλγόριθμος είναι άπληστος (greedy): σε κάθε βήμα, εξετάζει μόνο τους γειτονικούς ενός κόμβου (τοπικότητα). Βρίσκει τον κόμβο για τον οποίο έχει υπολογίσει την ελάχιστη διαδρομή και τον εισάγει στο σύνολο S, χρησιμοποιώντας πληροφορίες από προηγούμενα βήματα (σύνθεση). Στο τέλος δίνει ένα αποτέλεσμα για όλους τους κόμβους.

Σε βήματα

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

1. Σημείωσε σε κάθε κόμβο μια ετικέτα απόστασης (d[*]) με τιμή 0 στον αρχικό κόμβο και τιμή άπειρο σε όλους τους υπόλοιπους. Επίσης, σημείωσε μια ετικέτα προηγούμενου κόμβου (prev[*]) και βάλε της την κενή τιμή για όλους τους κόμβους. Η ετικέτα αυτή χρειάζεται για τον υπολογισμό της ζητούμενης διαδρομής στο τέλος.
2. Σημείωσε όλους τους κόμβους μη-επεξεργασμένους (${\displaystyle S=\emptyset }$). Ο τρέχων κόμβος είναι ο αρχικός.
3. Για τον τρέχοντα κόμβο, εξέτασε όλους τους μη-επεξεργασμένους γείτονές του και υπολόγισε το συνολικό άθροισμα απόστασής τους από τον αρχικό κόμβο. Για παράδειγμα, αν ο τρέχων κόμβος έχει απόσταση 6 από τον αρχικό και ο γείτονας του τρέχοντος κόμβου, που εξετάζει αυτή τη στιγμή ο αλγόριθμος, έχει απόσταση 2 από τον τρέχοντα, το συνολικό άθροισμα απόστασης του γείτονα από τον αρχικό κόμβο είναι 6+2=8. Αν αυτή η απόσταση είναι μικρότερη από την ετικέτα απόστασης που είχε σημειωθεί, αντικατάστησέ τη με τη νέα υπολογισμένη τιμή και σημείωσε τον τρέχοντα κόμβο στην ετικέτα προηγούμενου κόμβου.
4. Όταν τελειώσεις με την εξέταση όλων των γειτόνων του τρέχοντος κόμβου, σημείωσέ τον ως επεξεργασμένο. Ένας επεξεργασμένος κόμβος δεν εξετάζεται ποτέ ξανά από τον αλγόριθμο. Η ετικέτα απόστασής της είναι η ελάχιστη και θα παραμείνει σταθερή.
5. Ο επόμενος τρέχων κόμβος θα είναι ο μη-επεξεργασμένος κόμβος με τη μικρότερη ετικέτα απόστασης.
6. Αν όλοι οι κόμβοι έχουν σημειωθεί ως επεξεργασμένοι, προχώρα στο επόμενο βήμα. Διαφορετικά, συνέχισε από το βήμα 3.
7. Ξεκινώντας από τον κόμβο-προορισμό (ο οποίος είναι ο τελευταίος τρέχων κόμβος) εκτύπωσε τον κόμβο που αναγράφεται στην ετικέτα προηγούμενου κόμβου. Επανέλαβε μέχρι η ετικέτα προηγούμενο κόμβου που θα συναντήσεις να είναι άδεια.

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

Παράδειγμα

Στον πίνακα παρακάτω φαίνονται οι κινήσεις του αλγόριθμου για να βρει τη συντομότερη διαδρομή από τον κόμβο a προς τους υπόλοιπους. Τα d[*] και prev[*] είναι οι ετικέτες απόστασης και προηγούμενου κόμβου. Τα βάρη των ακμών στο σχήμα είναι οι αριθμοί δίπλα σε κάθε ακμή. Οι κόμβοι είναι αριθμημένοι με πεζούς λατινικούς χαρακτήρες.

Επανάληψη	S (επεξεργασμένοι)	(d[b], prev[b])	(d[c], prev[c])	(d[d], prev[d])	(d[e], prev[e])	(d[f], prev[f])	(d[g], prev[g])	(d[z], prev[z])	Κόμβος με το ελάχιστο d[*] στην Q
Αρχικοποίηση	{-}	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	a
1	{a}	(16, a)	(10, a)	(5, a)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	d
2	{a, d}	(16, a)	(9, d)	(5, a)	(20, d)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	c
3	{a, d, c}	(11, c)	(9, d)	(5, a)	(19, c)	(21, c)	(${\displaystyle \infty }$, -)	(${\displaystyle \infty }$, -)	b
4	{a, d, c, b}	(11, c)	(9, d)	(5, a)	(19, c)	(15, b)	(17, b)	(${\displaystyle \infty }$, -)	f
5	{a, d, c, b, f}	(11, c)	(9, d)	(5, a)	(18, f)	(15, b)	(17,b)	(31, f)	g
6	{a, d, c, b, f, g}	(11, c)	(9, d)	(5, a)	(18, f)	(15, b)	(17, b)	(24, g)	e
7	{a, d, c, b, f, g, e}	(11, c)	(9, d)	(5, a)	(18, f)	(15, b)	(17, b)	(23, e)	z

Η συντομότερη διαδρομή από τον a στον z έχει μήκος 23. Για να βρούμε τους κόμβους της ανάποδης διαδρομής, είμαστε στον κόμβο z και κοιτάζουμε την ετικέτα προηγούμενου κόμβου του, βλέπουμε τον κόμβο e και τον καταγράφουμε. Κοιτάζουμε την ετικέτα προηγούμενου κόμβου του e και βλέπουμε f και τον καταγράφουμε. Έπειτα, με τον ίδιο τρόπο πάμε από τον b στον c, μετά στον d και τέλος στον a. Επομένως, η σωστή διαδρομή είναι a-d-c-b-f-e-z. (Για ακόμα καλύτερη κατανόηση του αλγορίθμου, μπορείτε να δείτε το εξής video)

Ψευδοκώδικας

Ο παρακάτω ψευδοκώδικας έχει τρεις παραμέτρους:

1. Ένα γράφο G=(V,E) του οποίου το σύνολο κόμβων είναι το V και το σύνολο ακμών το E.
2. Μια δομή δεδομένων, w, που αναπαριστά τα βάρη των ακμών του γράφου.
3. Ο αρχικός κόμβος, s.

Στον παρακάτω αλγόριθμο διατηρείται ένα σύνολο S. Είναι το σύνολο των κόμβων για τους οποίους το συντομότερο μονοπάτι από την αφετηρία έχει υπολογιστεί. Πρόκειται ουσιαστικά για τους κόμβους που έχουν μαρκαριστεί ως επεξεργασμένοι. Με d[u] συμβολίζεται ένα άνω όριο για το βάρος της συντομότερης διαδρομής από τον αρχικό κόμβο s στον u. Στις περιγραφές που δώσαμε παραπάνω, το d[u] αντιστοιχούσε στην ετικέτα απόστασης. Για την ετικέτα προηγούμενου κόμβου ενός κόμβου v, χρησιμοποιείται ο συμβολισμός prev[v]. Επίσης, ο αλγόριθμος διατηρεί μια ουρά προτεραιότητας, Q, που περιέχει τους κόμβους του συνόλου V\S (V-S) με κλειδί τις τιμές d (τις ετικέτες απόστασης) του κάθε κόμβου.

Ντάικστρα(G,w,s)
Για κάθε κόμβο  {
    d[v]= άπειρο
    prev[v] = κενό
}
d[s]=0
Q = V

Όσο  {
    u = extract_min(Q)
    
    Για κάθε κόμβο v, γείτονα του κόμβου u, που δεν ανήκει στο S{
        Αν d[v]>d[u]+w[u,v] τότε
            d[v]=d[u]+w[u,v]
            prev[v] = u
    }
}

Η εντολή extract_min είναι πράξη της ουράς προτεραιότητας Q. Όλες οι ουρές προτεραιότητας έχουν μια πράξη για την εξαγωγή του μικρότερου στοιχείου (extract_min). To w[u,v] είναι το βάρος της ακμής που συνδέει τους κόμβους u και v.

Ο παρακάτω ψευδοκώδικας είναι για την εύρεση των κόμβων της συντομότερης διαδρομής, αφού έχει εφαρμοστεί ο παραπάνω ψευδοκώδικας και έχουν καθοριστεί οι αποστάσεις d και οι προηγούμενοι κόμβοι prev. Κατά την αρχικοποίηση της παρακάτω διαδικασίας, στις πρώτες δύο γραμμές, ο κόμβος u είναι ο κόμβος-προορισμός. Έπειτα, ακολουθώντας τις ενδείξεις prev, παίρνουμε τη ζητούμενη διαδρομή ανάποδα.

Α = κενή ακολουθία
Βάλε δείκτη στον κόμβο u
Όσο το prev[u] είναι διάφορο του κενού {
    Βάλε το u στην αρχή της Α
    u=prev[u]
}

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

Η χρονική πολυπλοκότητα του αλγόριθμου ποικίλλει ανάλογα με τον γράφο και τις δομές δεδομένων που χρησιμοποιούνται για την υλοποίησή του. Στη γενική περίπτωση, ο αλγόριθμος χρειάζεται χρόνο ${\displaystyle O(|V|m+(|V|+|E|)k)}$^[2], όπου V το σύνολο των κόμβων, E το σύνολο των ακμών του γράφου, m ο χρόνος που χρειάζεται για την εξαγωγή του μη-επεξεργασμένου κόμβου με την ελάχιστη ετικέτα απόστασης, δηλαδή την εφαρμογή της εντολής extract_min, και k ο χρόνος που χρειάζεται για την αλλαγή της ετικέτας απόστασης.

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

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

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

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

Η διαδρομή Ρ_v είναι αυτή που ξεκινά από τον κόμβο s και μέσω του κόμβου u φτάνει στον v. Επομένως, η διαδρομή Ρ_u περιέχεται στην Ρ_v. Η διαδρομή Π_v είναι αυτή που ξεκινά από τον κόμβο s, περνάει από τους x και y και καταλήγει στον v. Άρα, η Π_y περιέχεται στην Π_v και η Π_x στην Π_y.

Ο αλγόριθμος του Ντάικστρα είναι άπληστος (greedy), δηλαδή σε κάθε βήμα υπολογίζει την τοπικά βέλτιστη λύση. Στο τέλος, συνθέτει τις τοπικές λύσεις και επιστρέφει μια συνολική. Όμως, το γεγονός ότι οι τοπικές λύσεις είναι βέλτιστες δεν εγγυάται ότι και η σύνθεσή τους θα είναι μια συνολικά βέλτιστη λύση. Γι'αυτό είναι απαραίτητη μια απόδειξη ορθότητας του αλγορίθμου.

Έστω Ρ_v η διαδρομή που έχει σημειώσει ο αλγόριθμος από τον αρχικό κόμβο s στον κόμβο u. Θα δείξουμε ότι για κάθε κόμβο u του συνόλου S, σε κάθε στάδιο της εκτέλεσης του αλγόριθμου, η Ρ_v είναι η ελάχιστη διαδρομή. Αυτό μας δείχνει άμεσα ότι ο αλγόριθμος επιστρέφει τη βέλτιστη λύση, αφού στο τελευταίο βήμα το σύνολο S περιέχει όλους τους κόμβους του γραφήματος. Η απόδειξη είναι επαγωγική ως προς το μέγεθος του συνόλου S (των επεξεργασμένων κόμβων).

Για |S|=1, έχουμε ότι S={s} και το κόστος της διαδρομής Ρ_s είναι 0. Αφού δεν υπάρχουν αρνητικά βάρη, αυτή είναι όντως η συντομότερη διαδρομή. Έστω ότι για |S|=k, με k>1, ο ισχυρισμός ισχύει. Μένει να δείξουμε ότι ο ισχυρισμός ισχύει και για |S|=k+1, έχοντας αυξήσει το σύνολο των επεξεργασμένων κόμβων κατά 1, με την προσθήκη ενός κόμβου, έστω του v. Έστω ότι ο κόμβος u είναι ο αμέσως προηγούμενος του v στη διαδρομή Ρ_v που έχει σημειώσει ο αλγόριθμος. Λόγω της υπόθεσης της επαγωγής, η διαδρομή Ρ_u είναι η συντομότερη από τον αρχικό κόμβο στον u. Θεωρούμε, τώρα, οποιαδήποτε άλλη διαδρομή Π_v από τον αρχικό κόμβο στον v. Για να αποδείξουμε την πρόταση, αρκεί να δείξουμε ότι η Π_v έχει ίσο ή μεγαλύτερο κόστος από αυτό της Ρ_v.

Η οι κόμβοι της διαδρομής Π_v από ένα σημείο και μετά δεν ανήκουν στο σύνολο S. Υποθέτουμε ότι ο y είναι ο πρώτος κόμβος της Π_v που δεν ανήκει στο S και ότι ο αμέσως προηγούμενός του (που ανήκει στο S) είναι ο x. Κατά την επανάληψη k+1 του αλγόριθμου, εξετάζονται όλες οι διαδρομές από τον αρχικό κόμβο προς τους κόμβους που είναι γειτονικοί του S, δηλαδή εξετάζονται και η Ρ_v και η Π_y, αλλά υπολογίζοντας τα αντίστοιχα μήκη των διαδρομών και συκγρίνωντάς τα, προτιμάται η Ρ_v και τελικά στο σύνολο S προστίθεται ο κόμβος v. Αυτό σημαίνει ότι το μήκος της Ρ_v είναι ίσο ή μικρότερο από το μήκος της Π_y. Και αφού η Π_y είναι ένα μόνο μέρος της διαδρομής Π_v και δεν υπάρχουν αρνητικά βάρη, είναι προφανές ότι το μήκος της Π_v θα είναι κι αυτό ίσο ή μεγαλύτερο από το μήκος της Ρ_v.

Καθώς αυτό ισχύει για ολες τις πιθανές διαδρομές Π_v, έχουμε δείξει ότι η Ρ_v είναι η βέλτιστη.

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

Όπως έχει ήδη ίσως καταστεί εμφανές, ο αλγόριθμος του Ντάικστρα δεν λειτουργεί σωστά, αν κάποιες ακμές του γράφου έχουν αρνητικά βάρη. Σε έναν τέτοιο γράφο δεν εξασφαλίζεται ότι η λύση που δίνει ο αλγόριθμος είναι η βέλτιστη^[4]. Αυτό συμβαίνει λόγω της σημείωσης επεξεργασμένο που λαμβάνουν όλοι οι κόμβοι για τους οποίους έχει υπολογιστεί η συντομότερη διαδρομή από τον αρχικό κόμβο. Οι επεξεργασμένοι κόμβοι (αυτοί που ανήκουν στο σύνολο S) δεν εξετάζονται ξανά από τον αλγόριθμο. Έτσι, μια πιθανώς συντομότερη διαδρομή που θα μπορούσε να προκύψει (για έναν επεξεργασμένο κόμβο) μέσω μιας ακμής αρνητικού βάρους, δεν λαμβάνεται υπόψη.

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

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

Παραπομπές

1. Σχεδιασμός αλγορίθμων, John Kleinberg, Eva Tardos, 2008, σελ.173-175, ISBN 978-960-461-207-9
2. Algorithms, S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, 2006, σελ. 124-125
3. http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/dag_shortest_paths.html
4. http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html#dijkstra

Εξωτερικοί σύνδεσμοι

• Πολυμέσα σχετικά με το θέμα Dijkstra's algorithm στο Wikimedia Commons