Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra
Loading...
Date
2023-03-07
Authors
Καλλιφείδας, Νικόλαος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στην παρούσα διπλωματική εργασία γίνεται αρχικά μια ανάλυση του Αλγορίθμου Dijkstra που χρησιμεύει στην επίλυση προβλημάτων συντομότερων διαδρομών. Οι συντομότερες διαδρομές είναι ένα ζήτημα που μας απασχολεί συχνά στις μέρες μας είτε στην καθημερινή μας ζωή (καθημερινες αποστάσεις) ή και στην επιστήμη των υπολογιστών. Το πρόβλημα αυτό λύνει αποδοτικά ο Αλγόριθμος του Dijkstra όμως λόγω της πολυπλοκότητας του απαιτεί αρκετό χρόνο για να εκτελεστεί. Έτσι ένας τρόπος για να υλοποιηθεί πιο αποδοτικά είναι η χρήση του με ουρές προτεραιότητας. Έπειτα στην εργασία εχει υλοποιηθεί ο Αλγόριθμος με διαφορετικές ουρές προτεραιότητας και έχει γίνει εφαρμογή σε πραγματικά δεδομένα, δηλαδή οδικά δίκτυα των μεγαλουπόλεων των Ηνωμένων Πολιτείων της Αμερικής (ΗΠΑ) με σκοπό την εύρεση της πιο αποδοτικής ουράς βάσει συνθηκών όπως η απόσταση και το έγεθος του δικτύου. Τέλος έχουμε καταλήξει σε συμπεράσματα για τις ουρές προτεραιότητας και υπάρχει πλήρης επεξήγηση των υλοποιήσεων που κάναμε και των αποτελεσμάτων τους.
Description
Keywords
Αλγόριθμος Dijkstra, Ουρές προτεραιότητας, Συντομότερες διαδρομές, Γράφημα, Οδικά δίκτυα, Δέντρο