[Lab3] Priority Queue in C++ (Dijkstra)

Question

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

Answer 1

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

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

Comments

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