Ο αλγόριθμος του Dijkstra είναι αλγόριθμος γραφημάτων και χρησιμοποιείται, σε κατευθυνόμενα - εμβαρή γραφήματα για την εύρεση συντομότατων διαδρομών από έναν κόμβο προς όλους τους άλλους κόμβους ενός γραφήματος. Στον αλγόριθμο του Dijkstra απαγορεύονται οι ακμές με αρνητικά βάρη. Ο χρόνος εκτέλεσής του ποικίλει, ανάλογα με τον τύπο δεδομένων που θα χρησιμοποιήσουμε στην υλοποίηση του αλγορίθμου.
Ας τρέξουμε τον αλγόριθμο σε αυτό το γράφημα.
Αρχικά δημιουργούμε μία λίστα που περιέχει όλους τους μη εντοπισμένους κόμβους του γραφήματος μας. Επόμενο βήμα είναι να διαλέξουμε τον αρχικό κόμβο. Στο παράδειγμά μας, επιλέγουμε ως αρχικό κόμβο τον s.
Διαγράφουμε τον s από την λίστα των μη εντοπισμένων κόμβων.
Έπειτα, δημιουργούμε έναν πίνακα που θα περιέχει την απόσταση κάθε κόμβου από τον αρχικό κόμβο s. Βάζουμε την τιμή 0 στον αρχικό κόμβο s, αφού απαιτείται μηδενικό κόστος για να πάμε από τον s στον εαυτό του, και άπειρο για όλους τους άλλους κόμβους, μιας και δεν είναι ακόμη προσπελάσιμοι από αυτόν.
Ξεκινάμε να ελέγχουμε κάθε ακμή που εξέρχεται από τον s. Για κάθε τέτοια ακμή ελέγχουμε αν το κόστος του s συν το βάρος της ακμής, είναι μικρότερο από το κόστος του κόμβο που συνδέεται η ακμή και ανανεώνουμε τον πίνακά μας κατάλληλα. Η διαδικασία αυτή ονομάζεται πράξη χαλάρωσης. Μπορούμε να πάμε στους κόμβους a και b, με κόστος 4 και 2 αντίστοιχα. Και τα δύο κόστη είναι μικρότερα του απείρου, οπότε ας ανανεώσουμε τις τιμές του πίνακά μας.
Σε αυτό το σημείο διαλέγουμε τον κόμβο που έχει το μικρότερο κόστος και περιέχεται στην λίστα με τους μη εντοπισμένους κόμβους.
Αυτός ο κόμβος είναι ο c. Διαγράφουμε τον c από την λίστα και κοιτάζουμε πάλι τις εξερχόμενες ακμές του.
Ακολουθώντας την ίδια διαδικασία χαλάρωσης παρατηρούμε ότι για να πάμε από τον c στον a το συνολικό κόστος είναι 2 συν 1, 3 που είναι μικρότερο από το ήδη υπάρχον κόστος του a που είναι 4. Σε αυτή την περίπτωση ανανεώνουμε το κόστος του a με το νέο μικρότερο κόστος που είναι το 3.
Το ίδιο κάνουμε και για τους κόμβους b και d. Πλέον το κόστος του b είναι 9, αφού 2 που είναι το κόστος του c συν το 7 που είναι το βάρος της ακμής που συνδέει τον c με τον b ισούται με 9. και το νέο κόστος του d ισούται με 7.
Αφού ολοκληρώσαμε και με τον κόμβο c, επιλέγουμε όπως και πριν τον κόμβο που έχει το μικρότερο κόστος και περιέχεται στην λίστα με τους μη εντοπισμένους κόμβους. Αυτός ο κόμβος είναι ο a.
Διαγράφουμε τον κόμβο a και κοιτάμε τις εξερχόμενες ακμές του.
Μπορούμε να επισκεφτούμε τον κόμβο b με κόστος 5 και τον d με κόστος 9. Όμως θα ανανεώσουμε μόνο τον κόμβο b αφού το νέο κόστος του d δεν είναι μικρότερο του 7.
Επόμενος κόμβος που επιλέγουμε είναι ο b.
Ο b δεν περιέχει εξερχόμενες ακμές.
Ο τελευταίος κόμβος που θα εξετάσουμε είναι ο d.
Παρατηρούμε την ύπαρξη μίας εξερχόμενες ακμής που συνδέει τον d με τον s.
Το κόστος του d συν το βάρος της ακμής είναι 8, όμως δεν είναι μικρότερο από το κόστος του s οπότε δεν ανανεώνουμε τον πίνακα με τα κόστη μας ούτε σε αυτή την επανάληψη.
Έχουμε πλέον επισκεφτεί όλους τους κόμβους.
Το γράφημα που προκύπτει περιέχει τις συντομότατες διαδρομές από το τον αρχικό κόμβος s προς κάθε άλλον κόμβο.
Αυτός είναι ο αλγόριθμος σε μορφή ψευδοκώδικα. Αρχικά, παρατηρούμε ότι ο αλγόριθμος δέχεται τρεις παραμέτρους. Το γράφημα G στο οποίο θα εφαρμοστεί, μία συνάρτηση w που αντιστοιχεί βάρη σε ακμές και τον αρχικό κόμβο s.
Η εκτέλεση του αλγορίθμου ξεκινάει με την απόδοση αρχικών τιμών. Το πεδίο p δείχνει τον πατρικό ενός κόμβου. Το πεδίο d χρησιμοποιείται για να αποθηκεύσουμε την απόσταση του εκάστοτε κόμβου από τον αρχικό μας.
Ακολουθεί η δημιουργία του συνόλου S. Στο τέλος του αλγορίθμου το σύνολο S θα περιέχει όλους τους κόμβους του αρχικού γραφήματος G.
Επόμενο βήμα είναι η δημιουργία της ουράς προτεραιότητας ελαχίστων. Με αυτό τον τρόπο θα μπορούμε να επιλέγουμε κάθε φορά την ακμή με το ελάχιστο βάρος.
Ο αλγόριθμος θα πρέπει να συνδέσει όλους τους κόμβους του γραφήματος. Ο βρόγχος while ελέγχει αν υπάρχουν ακόμα κόμβοι στην ουρά Q.
Σε κάθε επανάληψη του βρόγχου while εξάγουμε τον κόμβο με το μικρότερο κόστος. Αυτός ο τρόπος διασφαλίζει και την περατότητα του βρόγχου while.
Προσθέτουμε τον κόμβο u στο σύνολο S.
Για κάθε κόμβο v που συνδέεται με u, ελέγχουμε αν το κόστος του κόμβου v είναι μεγαλύτερο από το βάρος της ακμής που συνδέει τον u με τον v συν το κόστος του u. Αν ναι τότε ανανεώνουμε το κόστος του d και θέτουμε ως πατρικό του το u. Μέσω των πατρικών κόμβων μπορούμε αργότερα να προσπελάσουμε όλους τους κόμβους.
Οι γραμμές 1 έως 5 έχουμε πολυπλοκότητα O(V) διότι έχουμε έναν επαναληπτικό βρόγχο που εκτελεί τόσες επαναλήψεις, όσες είναι ο αριθμός των κόμβων του γραφήματος. Οι αρχικοποίηση στις γραμμές 4 και 5 εκτελούνται σε σταθερό χρόνο.
Για την δημιουργία της ουράς προτεραιότητας ελαχίστων απαιτείτε χρόνος O(V) αν υλοποιηθεί με δυαδικό σωρό ή σωρό Fibonacci.
Η γραμμή 7 θα εκτελεστεί O(V) φορές, όσες δηλαδή το πλήθος των κόμβων του γραφήματος.
Η εξαγωγή στοιχείου από την ουρά Q απαιτεί συνολικό χρόνο O(V^2) αν υλοποιηθεί με πίνακα, διαφορετικά O(VlogV) αν υλοποιηθεί με δυαδικό σωρό και σωρό Fibonacci.
Η προσθήκη του κόμβου u στο σύνολο S στην γραμμή 10 απαιτεί χρόνο O(V).
Οι γραμμές 11 έως 14 θα εκτελεστούν συνολικά O(V^2) αν η υλοποίηση του γραφήματος γίνει με πίνακα γειτνίασης, O(ElogV) αν γίνει με δυαδικό σωρό και O(E + VlogV) αν υλοποιηθεί με σωρό Fibonacci.
