Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra
Στην παρούσα διπλωματική εργασία γίνεται αρχικά μια ανάλυση του Αλγορίθμου Dijkstra που χρησιμεύει στην επίλυση προβλημάτων συντομότερων διαδρομών. Οι συντομότερες διαδρομές είναι ένα ζήτημα που μας απασχολεί συχνά στις μέρες μας είτε στην καθημερινή μας ζωή (καθημερινες αποστάσεις) ή και στην επιστ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2023
|
| Θέματα: | |
| Διαθέσιμο Online: | https://hdl.handle.net/10889/24808 |
| id |
nemertes-10889-24808 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-248082023-03-14T04:35:16Z Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra Priority queues for a more efficient implementation of Dijkstra's algorithm Καλλιφείδας, Νικόλαος Kallifeidas, Nikolaos Αλγόριθμος Dijkstra Ουρές προτεραιότητας Συντομότερες διαδρομές Γράφημα Οδικά δίκτυα Δέντρο Binary heap Sequence heap Pairing heap Στην παρούσα διπλωματική εργασία γίνεται αρχικά μια ανάλυση του Αλγορίθμου Dijkstra που χρησιμεύει στην επίλυση προβλημάτων συντομότερων διαδρομών. Οι συντομότερες διαδρομές είναι ένα ζήτημα που μας απασχολεί συχνά στις μέρες μας είτε στην καθημερινή μας ζωή (καθημερινες αποστάσεις) ή και στην επιστήμη των υπολογιστών. Το πρόβλημα αυτό λύνει αποδοτικά ο Αλγόριθμος του Dijkstra όμως λόγω της πολυπλοκότητας του απαιτεί αρκετό χρόνο για να εκτελεστεί. Έτσι ένας τρόπος για να υλοποιηθεί πιο αποδοτικά είναι η χρήση του με ουρές προτεραιότητας. Έπειτα στην εργασία εχει υλοποιηθεί ο Αλγόριθμος με διαφορετικές ουρές προτεραιότητας και έχει γίνει εφαρμογή σε πραγματικά δεδομένα, δηλαδή οδικά δίκτυα των μεγαλουπόλεων των Ηνωμένων Πολιτείων της Αμερικής (ΗΠΑ) με σκοπό την εύρεση της πιο αποδοτικής ουράς βάσει συνθηκών όπως η απόσταση και το έγεθος του δικτύου. Τέλος έχουμε καταλήξει σε συμπεράσματα για τις ουρές προτεραιότητας και υπάρχει πλήρης επεξήγηση των υλοποιήσεων που κάναμε και των αποτελεσμάτων τους. In this thesis, an analysis of the Dijkstra Algorithm is first performed, which is used to solve shortest path problems. Shortest routes are an issue that often concerns us nowadays either in our daily life (daily distances) or in computer science. Dijkstra's Algorithm solves this problem efficiently, but due to its complexity, it requires a lot of time to execute. So one way to implement it more efficiently is to use it with priority queues. Then in the paper, the Algorithm has been implemented with different priority queues and it has been applied to real data, that is, road networks of the big cities of the United States of America (USA) in order to find the most efficient queue based on conditions such as distance and network size . Finally we have reached conclusions about priority queues and there is a full explanation of the implementations we did and their results. 2023-03-13T11:26:53Z 2023-03-13T11:26:53Z 2023-03-07 https://hdl.handle.net/10889/24808 el application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Αλγόριθμος Dijkstra Ουρές προτεραιότητας Συντομότερες διαδρομές Γράφημα Οδικά δίκτυα Δέντρο Binary heap Sequence heap Pairing heap |
| spellingShingle |
Αλγόριθμος Dijkstra Ουρές προτεραιότητας Συντομότερες διαδρομές Γράφημα Οδικά δίκτυα Δέντρο Binary heap Sequence heap Pairing heap Καλλιφείδας, Νικόλαος Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra |
| description |
Στην παρούσα διπλωματική εργασία γίνεται αρχικά μια ανάλυση του Αλγορίθμου Dijkstra που χρησιμεύει στην επίλυση προβλημάτων συντομότερων διαδρομών. Οι συντομότερες διαδρομές είναι ένα ζήτημα που μας απασχολεί συχνά στις μέρες μας είτε στην καθημερινή μας ζωή (καθημερινες αποστάσεις) ή και στην επιστήμη των υπολογιστών. Το πρόβλημα αυτό λύνει αποδοτικά ο Αλγόριθμος του Dijkstra όμως λόγω της πολυπλοκότητας του απαιτεί αρκετό χρόνο για να εκτελεστεί. Έτσι ένας τρόπος για να υλοποιηθεί πιο αποδοτικά είναι η χρήση του με ουρές προτεραιότητας. Έπειτα στην εργασία εχει υλοποιηθεί ο Αλγόριθμος με διαφορετικές ουρές προτεραιότητας και έχει γίνει εφαρμογή σε πραγματικά δεδομένα, δηλαδή οδικά δίκτυα των μεγαλουπόλεων των Ηνωμένων Πολιτείων της Αμερικής (ΗΠΑ) με σκοπό την εύρεση της πιο αποδοτικής ουράς βάσει συνθηκών όπως η απόσταση και το έγεθος του δικτύου. Τέλος έχουμε καταλήξει σε συμπεράσματα για τις ουρές προτεραιότητας και υπάρχει πλήρης επεξήγηση των υλοποιήσεων που κάναμε και των αποτελεσμάτων τους. |
| author2 |
Kallifeidas, Nikolaos |
| author_facet |
Kallifeidas, Nikolaos Καλλιφείδας, Νικόλαος |
| author |
Καλλιφείδας, Νικόλαος |
| author_sort |
Καλλιφείδας, Νικόλαος |
| title |
Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra |
| title_short |
Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra |
| title_full |
Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra |
| title_fullStr |
Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra |
| title_full_unstemmed |
Ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του Dijkstra |
| title_sort |
ουρές προτεραιότητας για αποδοτικότερη υλοποίηση του αλγορίθμου του dijkstra |
| publishDate |
2023 |
| url |
https://hdl.handle.net/10889/24808 |
| work_keys_str_mv |
AT kallipheidasnikolaos ouresproteraiotētasgiaapodotikoterēylopoiēsētoualgorithmoutoudijkstra AT kallipheidasnikolaos priorityqueuesforamoreefficientimplementationofdijkstrasalgorithm |
| _version_ |
1771297145290227712 |
