Εργαστήριο Τεχνολογίας Λογισμικού
0 votes
311 views

Γεια σας,
Προσπάθησα να υλοποιήσω τον αλγόριθμο Dijkstra στην c++ και ήμουν ιδιαίτερα χαρούμενος όταν είδα ότι υπάρχει ήδη priority queue στην stl. Όμως βρέθηκα προ εκπλήξεως γιατί η priority queue στην STL δεν κάνει αυτά που θα ήθελε ο Dijkstra. Συγκεκριμένα δεν μπορεί να ανανεώσει τα κλειδιά (Decrease Key). Τι μου προτείνετε σαν εναλλακτική;

in algorithms by (730 points) | 311 views

1 Answer

+1 vote

Δυστυχώς η μοναδική απάντηση είναι να την υλοποιήσεις μόνος σου :)

Δεν είναι δύσκολο να υλοποιήσεις από την αρχή μία priority queue με decrease key. Από την άλλη είναι πολύ δύσκολο να υλοποιηθεί και σωστά, και αποδοτικά αλλά και να είναι generic. Μάλιστα χρειάζεται μόνο σε πολύ λίγες περιπτώσεις, συγκεκριμένα στον ... Dijkstra. Για αυτό και δεν θα τη συναντήσεις σε καμία στάνταρ βιβλιοθήκη.

by (800 points)
0

Ευχαριστώ για την απάντηση! Όντως μάλλον αυτή είναι η καλύτερη λύση για μία δομή με την δυνατότητα DecreaseKey. Προσωπικά έχοντας παρακολουθήσει το μάθημα δεν μου φαίνεται κατ ανάγκην δύσκολη αυτή η υλοποίηση αλλά πάντως όχι προφανής (χωρίς να χάσουμε τα καλά του δυαδικού σωρού). Όμως όσο το έψαξα για τα πλαίσια της άσκησης μάλλον η καλύτερη λύση είναι η τεχνική Lazy Deletion.

301 questions

289 answers

288 comments

894 users