Κατανόηση του όλου Ζευγάρι μικρότερο πρόβλημα διαδρομής

Το πρόβλημα της συντομότερης διαδρομής όλων των ζευγών (APSP) επιδιώκει τη μικρότερη απόσταση μεταξύ κάθε ζεύγους κορυφών σε ένα σταθμισμένο γράφημα. Είναι μια θεμελιώδης πρόκληση στη θεωρία γραφημάτων με άμεσες επιπτώσεις για το σχεδιασμό του δικτύου, τη βελτιστοποίηση της ροής της κυκλοφορίας, την ανάλυση του κοινωνικού δικτύου, και την εφοδιαστική. Σε αντίθεση με τα προβλήματα της διαδρομής με ένα μόνο εργαλείο, η επίλυση APSP απαιτεί υπολογιστικές αποστάσεις από κάθε κορυφή προς όλα τα άλλα, η οποία κλιμακώνεται τετραγωνικά με τον αριθμό των κόμβων.

Οι κοινές προσεγγίσεις αντιμετωπίζουν αυτό το πρόβλημα αλλά αντιμετωπίζουν συναλλαγές ⁇ offs. Floyd-Warshall, ένας δυναμικός αλγόριθμος προγραμματισμού, λειτουργεί σε πυκνά γραφήματα αλλά τρέχει σε [[LFT:0]]O(V3]][[[LFT:3]]] χρόνο και δεν μπορεί να χειριστεί κύκλους αρνητικού βάρους. Ο αλγόριθμος της Dijkstra, όταν τρέχει από κάθε vertex, επιτυγχάνει [O(V (E + V log V))][[LFT:5]] με ένα δυαδικό σωρό, αλλά αποτυγχάνει σε γραφήματα με αρνητικά βάρη άκρων. Για αραιά γραφήματα, ο αλγόριθμος του Johnson γεφυρώνει αυτό το χάσμα συνδυάζοντας τις καλύτερες από τις δύο μεθόδους ενώ χειρίζεται αρνητικά βάρη ⁇ δεν παρέχονται αρνητικοί κύκλοι υπάρχουν.

Σύγκριση των κοινών αλγορίθμων

Για να εκτιμήσετε τον αλγόριθμο του Τζόνσον, βοηθά να αντιπαραβάλετε τους πιο συχνά χρησιμοποιούμενους λύτες APSP:

  • Floyd-Warshall ⁇ Απλό να εφαρμοστεί, χρησιμοποιεί μια 2D μήτρα απόστασης, ενημερώσεις μέσω τριπλών βρόχων. Λειτουργεί σε αρνητικές ακμές αλλά όχι αρνητικούς κύκλους. Απλοίαστη για γραφήματα με χιλιάδες κορυφές λόγω κυβικού χρόνου.
  • Επαναλαμβανόμενη Dijkstra ⁇ Τρέχει Dijkstra από κάθε κορυφή. Γρήγορος σε αραιά γραφήματα (]O(V E log V) χρησιμοποιώντας σωρούς Fibonacci), αλλά περιορίζεται σε μη αρνητικά βάρη.
  • Bellman-Ford (επαναλαμβανόμενο)[ ⁇ Χειρίζεται αρνητικές ακμές αλλά τρέχει σε O(V2E)], που είναι βραδύτερο και από τις δύο εναλλακτικές λύσεις.
  • Αλγόριθμος Johnson ⁇ Επαναβαρύνει το γράφημα ώστε όλες οι άκρες να γίνουν μη αρνητικές, στη συνέχεια εφαρμόζεται επαναλαμβανόμενη Dijkstra. Αποδίδει O(V E + V2 log V) με δυαδικό σωρό, καθιστώντας την προτιμώμενη επιλογή για αραιά γραφήματα με αρνητικά βάρη.

Πώς Λειτουργεί ο Αλγόριθμος του Τζόνσον

Ο αλγόριθμος του Johnson μετατρέπει έξυπνα ένα γράφημα που περιέχει αρνητικές άκρες σε ένα με μόνο μη αρνητικά βάρη άκρων, διατηρώντας τη δομή των συντομότερων μονοπατιών. Αυτή η μετατροπή βασίζεται σε μια [[LFT:0]]δυνατή λειτουργία[[LFT:1]] που προέρχεται από μια ενιαία εκτέλεση του Bellman ⁇ Ford. Μόλις επανασταθμιστεί, ο αλγόριθμος Dijkstra μπορεί να χρησιμοποιηθεί από κάθε κόμβο με ασφάλεια. Ο αλγόριθμος αποτελείται από τέσσερα βήματα.

Βήμα 1: Προσθήκη ενός κόμβου Super Source

Στο γράφημα προστίθεται νέα κορυφή s, συνδεδεμένη με κάθε υπάρχουσα κορυφή με άκρο βάρους 0. Αυτός ο επιπλέον κόμβος δεν μεταβάλλει τις συντομότερες αποστάσεις διαδρομής, διότι οποιαδήποτε διαδρομή που χρησιμοποιεί s μπορεί να προσαρτηθεί χωρίς κόστος.

Βήμα 2: Υπολογίζοντας πιθανές λειτουργίες με Bellman-Ford

Εκτελέστε τον αλγόριθμο Bellman ⁇ Ford από την υπερπηγή s. Επειδή s έχει μηδενικές άκρες σε όλες τις κορυφές, ο αλγόριθμος υπολογίζει τη μικρότερη απόσταση h(v)] από [s σε κάθε vertex v]. Αυτή η απόσταση χρησιμεύει ως πιθανή συνάρτηση. Αν ένας αρνητικός κύκλος ανιχνευθεί κατά τη διάρκεια αυτής της διαδρομής, το αρχικό γράφημα περιέχει αρνητικό κύκλο, και ο αλγόριθμος του Johnson αναφέρει ότι δεν υπάρχει έγκυρο σύνολο συντομότερων μονοπατιών.

Βήμα 3: Επαναστάθμιση του Γράφματος

Χρησιμοποιώντας τις δυνατότητες h(v), κάθε άκρο (u, v) με αρχικό βάρος w(u, v) επανσταθμίζεται σε:

w'(u, v) = w(u, v) + h(u) ⁇ h(v)

Η μετατροπή αυτή εγγυάται ότι κάθε σταθμισμένο βάρος άκρου δεν είναι αρνητικό. Η απόδειξη βασίζεται στην ανισότητα τριγώνου: επειδή h(v) ≤ h(u) + w(u, v) (από την έξοδο Bellman ⁇ Ford), προκύπτει ότι w'(u, v) ≥ 0]. Επιπλέον, διατηρείται η παραγγελία μονοπατιών: η συντομότερη διαδρομή μεταξύ δύο κορυφών στο αρχικό γράφημα παραμένει η συντομότερη διαδρομή στο επανασταθμισμένο γράφημα.

Βήμα 4: Εκτέλεση του Αλγόριθμου της Ντιτζκστρά από κάθε Βέρτεξ

Με το ανασταθμισμένο γράφημα που περιέχει μόνο μη αρνητικές άκρες, ο αλγόριθμος Dijkstra εκτελείται μία φορά από κάθε κορυφή. Κάθε εκτέλεση υπολογίζει τις συντομότερες αποστάσεις σε όλες τις άλλες κορυφές. Οι προκύπτουσες αποστάσεις μετατρέπονται στη συνέχεια πίσω σε αρχικά βάρη άκρων χρησιμοποιώντας τον τύπο:

dist original(u, v) = distre σταθμισμένη(u, v) ⁇ h(u) + h(v)

Το τελικό αυτό βήμα εξασφαλίζει ότι οι αναφερόμενες αποστάσεις είναι ακριβείς για το αρχικό γράφημα.

Πολυπλοκότητα και Ανάλυση Επιδόσεων

Ο αλγόριθμος του Johnson επιτυγχάνει μια συνολική χρονική πολυπλοκότητα O(V E + V2 log V] όταν υλοποιείται με μια σειρά προτεραιότητας δυαδικών σωρών. Το βήμα Bellman ⁇ Ford τρέχει σε O(V E)] και το επόμενο V Η Dijkstra τρέχει κάθε λήψη O(E + V log V V) σε αραιά γραφήματα. Για πυκνά γραφήματα O(V:10]E ⁇ είναι ένας από τους πιο αποτελεσματικούς πίνακες ή ], οι προσεγγίσεις πολυπλοκότητας , ωστόσο , είναι οι , οι προσεγγίσεις , [FLT:[LT:]

Χρησιμοποιώντας ένα σωρό Fibonacci μπορεί να μειώσει το μέρος της Dijkstra σε O(V E + V2 log V) αποσβέστηκε, αν και στην πράξη οι δυαδικοί σωροί είναι απλούστεροι και συχνά αρκετά γρήγοροι. Το αποτύπωμα μνήμης είναι O(V2] για τη μήτρα απόστασης, αλλά αυτό μπορεί να βελτιωθεί με την έμμεση αποθήκευση αποτελεσμάτων.

Πρακτικές εφαρμογές

Ο αλγόριθμος Johnson χρησιμοποιείται σε τομείς όπου οι άκρες γραφημάτων μπορεί να φέρουν αρνητικό κόστος και όλες ⁇ ζευγάρι μικρότερες αποστάσεις απαιτούνται.

  • ⁇ υθμίσεις δικτύου: Οι πάροχοι υπηρεσιών διαδικτύου και τα τηλεπικοινωνιακά δίκτυα χρησιμοποιούν κατανεμημένα πρωτόκολλα δρομολόγησης που πρέπει να υπολογίζουν προσαρμοστικά τη φθηνότερη διαδρομή μεταξύ των δύο δρομολογητών, ακόμη και όταν το κόστος σύνδεσης κυμαίνεται ή γίνεται αρνητικό (π.χ., λόγω συμφόρησης ή εκπτώσεων πολιτικής).
  • Αστικός σχεδιασμός μεταφορών: Χαρτογράφηση και εφοδιαστική εταιρείες (π.χ., Google Maps, OpenStreetMap routing motores) υπολογίστε συντομότερες διαδρομές μεταξύ πολλών προελεύσεων ⁇ προορισμών ζευγών για βελτιστοποίηση στόλου. Αρνητικά βάρη μπορούν να μοντελοποιήσουν επιδοτήσεις ή εκπτώσεις χρόνου.
  • Ελαχιστοποίηση κόστους αλυσίδας προμήθειας:[[LFT:1]] Σε δίκτυα παραγωγής πολλαπλών σταδίων, το κόστος από έναν κόμβο σε έναν άλλο μπορεί να είναι αρνητικό (π.χ., εκπτώσεις). Ο αλγόριθμος του Τζόνσον βρίσκει τις πιο κερδοφόρες διαδρομές σε ολόκληρη την αλυσίδα εφοδιασμού.
  • Ανάλυση κοινωνικού δικτύου: Η μέτρηση της συγκέντρωσης ή της μεταξύ τους κεντρικής κατάστασης απαιτεί όλες τις αποστάσεις ⁇ ζευγών. Οι αρνητικές άκρες μπορούν να αντιπροσωπεύουν τους συνδέσμους εκπτώσεων «φίλος ⁇ ενός ⁇ φίλου» ή τις σχέσεις αντιστοίχων.
  • Οικονομικές εισροές-εξόδου μοντέλα: Τα μοντέλα και οι αναλύσεις ροής της Leontief συχνά περιλαμβάνουν αρνητικούς συντελεστές· ο αλγόριθμος του Johnson υπολογίζει το καθαρό αποτέλεσμα των πολλαπλασιαστικών αλλαγών μέσω μιας διασυνδεδεμένης οικονομίας.

Για περαιτέρω ανάγνωση των μαθηματικών θεμελίων, βλέπε ] και την αρχική εργασία του Donald B. Johnson (1977). Μια πρακτική εφαρμογή στην Python μπορεί να βρεθεί στο Το αποθετήριο GitHub του NetworkX, το οποίο περιλαμβάνει τον αλγόριθμο του Johnson ως τυπική λειτουργία. Για μια βαθύτερη κατανόηση της τεχνικής επαναστάθμισης, CP ⁇ Algorithms παρέχει ένα σαφές βήμα ⁇ προς ⁇ βήμα tutorial]].

Συμπέρασμα

Ο αλγόριθμος του Johnson ξεχωρίζει ως μια κομψή και πρακτική λύση για το πρόβλημα όλων ⁇ ζευγών συντομότερου διαδρομής όταν υπάρχουν αρνητικά βάρη άκρη. Συνδυάζοντας την ευρωστία του Bellman ⁇ Ford (για την ανίχνευση αρνητικών κύκλων και υπολογιστικών δυνατοτήτων) με την ταχύτητα του Dijkstra (για μη αρνητικά γραφήματα), επιτυγχάνει εξαιρετική απόδοση σε αραιά δίκτυα. Η ίδια η τεχνική επαναστάθμισης είναι μια όμορφη εφαρμογή των πιθανών λειτουργιών ⁇ μια έννοια που εκτείνεται πολύ πέρα από συντομότερες διαδρομές σε περιοχές όπως ελάχιστη ⁇ κόστος ροής και θεωρία αλγοριθμικών παιχνιδιών.

Όταν αντιμετωπίζει ένα πραγματικό - παγκόσμιο πρόβλημα APSP όπου τα γραφήματα είναι αραιά και μπορεί να περιέχουν αρνητικές άκρες, ο αλγόριθμος του Τζόνσον θα πρέπει να είναι η πρώτη εξέταση. Οι θεωρητικές εγγυήσεις και η ευρεία εφαρμογή του στις βιβλιοθήκες (π.χ., ]NetworkX], Boost Graph Library]]) καθιστούν πρακτική την υιοθέτηση.