Ο Αλγόριθμός Dijkstra

εύρεσης της συντομότερης διαδρομής

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

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