Στη μαθηματική επιστήμη και την πληροφορική εκείμια ξεχωριστή περιοχή που ονομάζεται γράφημα θεωρία. Στο πλαίσιο του, τίθενται και επιλύονται διάφορα προβλήματα, για παράδειγμα, για την εύρεση της μικρότερης διαδρομής μεταξύ των κορυφών. Μία από τις μεθόδους που διαδίδονται μεταξύ των μαθηματικών για την επίλυση αυτού του προβλήματος ήταν εδώ και καιρό ο αλγόριθμος της Dijkstra.
Πιστεύεται ότι η έννοια του γραφήματος εισήχθη στοκαθημερινή ζωή του δέκατου όγδοου αιώνα από τον Leonard Euler. Αυτός ήταν που εξέφρασε τη διατύπωση και τη λύση ενός από τα κλασικά προβλήματα αυτής της θεωρίας - για τις επτά γέφυρες του Koenigsberg. Για να εξηγήσουν το αντικείμενο αυτής της θεωρίας, συχνά χρησιμοποιούν μια αναλογία, όπως η κίνηση μεταξύ διαφορετικών πόλεων. Στη συνέχεια, το γράφημα στο επίπεδο θα αντιπροσωπεύει ολόκληρο το σχήμα διαδρομής, όπου τα σημεία θα είναι συγκεκριμένα σημεία (για παράδειγμα, πόλεις) και τα άκρα θα είναι τα μονοπάτια από τη μια κορυφή στην άλλη (ένα ανάλογο του δρόμου μεταξύ πόλεων). Ο αλγόριθμος της Dijkstra, μεταξύ άλλων τρόπων, μπορεί να δώσει λύση σε αυτό το ζήτημα.
Ένα από τα τυπικά προβλήματα στη θεωρία γραφημάτων είναιένα στο οποίο πρέπει να καθορίσετε τη βέλτιστη διαδρομή κόστους μεταξύ δύο σημείων. Μπορεί να μειωθεί στο επίπεδο της λύσης του γραφήματος, στο οποίο οι κορυφές - πόλεις - διασυνδέονται από άκρα, που είναι πιθανοί δρόμοι. Επιπλέον, κάθε δρόμος έχει το δικό του μήκος, επομένως, για να διασχίσει θα πρέπει να δαπανήσει ορισμένα χρήματα. Αυτό το άθροισμα είναι ισοδύναμο με το βάρος του άκρου στο γράφημα. Στη συνέχεια, το έργο στην πράξη μπορεί να διατυπωθεί ως εξής: πώς να ανοίξει το δρόμο από τη μια πόλη στην άλλη προκειμένου να δαπανήσουν ελάχιστα χρήματα στο δρόμο.
Λύσεις
Για να λυθεί αυτό το πρόβλημα, μερικάαλγόριθμοι που έχουν γίνει ευρέως γνωστοί στον επιστημονικό κόσμο. Για παράδειγμα, ο αλγόριθμος Floyd-Warshell, Ford-Bellman. Ο κλασικός τρόπος εξεύρεσης λύσης είναι επίσης ο αλγόριθμος της Dijkstra. Μπορεί να χρησιμοποιηθεί τόσο για ένα σταθμισμένο (το βάρος κάθε άκρης είναι γνωστό) γράφημα όσο και για ένα αραιό. Για να βρείτε την τελική διαδρομή, πρέπει να κάνετε μερικά βήματα.
Ο Αλγόριθμος της Dijkstra
Η έννοια αυτής της μεθόδου είναι αυτήόλες οι κορυφές διασχίζονται, ξεκινώντας από τη δεδομένη, και σε κάθε μια έχει μια ετικέτα με μια συγκεκριμένη τιμή. Στη συνέχεια, οι κορυφές των οποίων οι ετικέτες είναι ελάχιστες περιλαμβάνονται στο αποτέλεσμα. Στο πρώτο βήμα, στην αρχική κορυφή εκχωρείται μια ετικέτα με την τιμή 0. Στη συνέχεια λαμβάνονται υπόψη όλες οι ακόλουθες κορυφές, δηλαδή αυτές που μπορούν να επιτευχθούν από το πρωτότυπο. Εκχωρούνται ετικέτες, η τιμή των οποίων ορίζεται ως το άθροισμα της πηγής και το βάρος της διαδρομής. Από τις κορυφές του επόμενου βήματος, επιλέξτε αυτήν που έχει τη λιγότερη τιμή ετικέτας και εξετάστε όλες τις κορυφές στις οποίες μπορείτε να μεταβείτε από αυτήν χωρίς να χρησιμοποιήσετε ενδιάμεσες κορυφές. Ορίζεται μια νέα τιμή ετικέτας, ίση με την ετικέτα κορυφής - την πηγή, συν το βάρος της διαδρομής. Εάν η ληφθείσα τιμή είναι μικρότερη από την ετικέτα κορυφής, τότε η ετικέτα αλλάζει. Διαφορετικά, η αρχική τιμή παραμένει. Σε αυτήν την περίπτωση, σε ξεχωριστό πίνακα, η διάσταση του οποίου ισούται με τον αριθμό κορυφών του γραφήματος, το αποτέλεσμα βελτιστοποίησης αποθηκεύεται, με τον οποίο καθορίζεται η διαδρομή. Για να εφαρμόσει μια μέθοδο όπως ο αλγόριθμος Dijkstra, η Pascal προσφέρει πολύ βολικά εργαλεία. Ο αλγόριθμος έχει το πλεονέκτημα ότι μπορεί εύκολα να αποτελέσει τη βάση ενός προγράμματος μικρού μεγέθους. Παραδείγματα τέτοιων προϊόντων λογισμικού είναι εύκολο να βρεθούν στο Διαδίκτυο.
