Ναι, έχετε δίκιο Ο αλγόριθμος του Prim λειτουργεί όπως ο αλγόριθμος του dijkstra, αλλά στον αλγόριθμο του prim δεν θα πρέπει να υπολογίζει τη συντομότερη διαδρομή από το i στο j με αρνητικές ακμές. Έτσι, είναι ένας άλλος αλγόριθμός τους, δηλαδή ο αλγόριθμος Bellman-Ford για τον υπολογισμό της συντομότερης διαδρομής από το i στο j με αρνητική ακμή.
Γιατί λειτουργεί ο αλγόριθμος του Prim;
Στην επιστήμη των υπολογιστών, ο αλγόριθμος του Prim (επίσης γνωστός ως αλγόριθμος του Jarník) είναι ένας άπληστος αλγόριθμος που βρίσκει ένα ελάχιστο εκτεινόμενο δέντρο για ένα σταθμισμένο μη κατευθυνόμενο γράφημα Αυτό σημαίνει ότι βρίσκει ένα υποσύνολο οι άκρες που σχηματίζουν ένα δέντρο που περιλαμβάνει κάθε κορυφή, όπου το συνολικό βάρος όλων των άκρων του δέντρου ελαχιστοποιείται.
Είναι σωστός ο αλγόριθμος του Prim;
Απόδειξη ορθότητας
Αποδεικνύουμε ότι ο αλγόριθμος του Prim είναι σωστός με την επαγωγή στο αναπτυσσόμενο δέντρο που κατασκευάστηκε από τον αλγόριθμο. … Αποδεικνύουμε με συστολή ότι το Ti είναι μέρος ενός ελάχιστα εκτεινόμενου δέντρου. Έστω ei=(v, u) η ακμή που βρέθηκε από τον αλγόριθμο του Prim και υποθέστε ότι δεν είναι ακμή ενός ελάχιστου δέντρου που εκτείνεται.
Πόσο αποτελεσματικός είναι ο αλγόριθμος του Prim;
Ο αλγόριθμος του Prim λειτουργεί αποτελεσματικά εάν κρατήσουμε μια λίστα d[v] με τα φθηνότερα βάρη που συνδέουν μια κορυφή, v, η οποία δεν βρίσκεται στο δέντρο, με οποιαδήποτε κορυφή ήδη στο δέντρο. …
Λειτουργούν τα Prims με αρνητικά βάρη;
Κάνει Prim's; Λύση: Yes, και οι δύο αλγόριθμοι λειτουργούν με αρνητικά βάρη άκρων επειδή η ιδιότητα αποκοπής εξακολουθεί να ισχύει.
