Αλγόριθμος Push-Relabel
Ο Αλγόριθμος Push-Relabel, που αναπτύχθηκε από τους Andrew V. Goldberg και Robert E. Tarjan το 1988, είναι μια εξαιρετικά αποδοτική μέθοδος για τον υπολογισμό της μέγιστης ροής σε δίκτυα. Σε αντίθεση με τις μεθόδους επαύξησης μονοπατιών, διατηρεί μια προ-ροή (preflow) και χρησιμοποιεί τοπικές λειτουργίες ώθησης (push) και καθολικής επανα-ετικετοποίησης (relabel) για να κατευθύνει τη ροή προς τον κόμβο προορισμού, επιτυγχάνοντας ανώτερη πολυπλοκότητα στη χειρότερη περίπτωση.
Διαβάστε ολόκληρη τη μέθοδο
Συνδεθείτε με δωρεάν λογαριασμό για να διαβάσετε αυτή την ενότητα.
Method map
The neighbourhood of related methods — select a node to explore.
Πηγές
- Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of the ACM, 35(4), 921-940. DOI: 10.1145/48014.61051 ↗
- Goldberg, A. V. (1998). Recent advances in maximum flow and minimum-cost flow algorithms. In Algorithm Theory (pp. 1-10). Springer, Berlin. link ↗
Πώς να παραπέμψετε σε αυτή τη σελίδα
ScholarGate. (2026, June 3). Push-Relabel Algorithm for Maximum Flow. ScholarGate. https://scholargate.app/el/operations-research/push-relabel-algorithm
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Αλγόριθμος Bellman-FordΕπιχειρησιακή Έρευνα↔ compare
- Αλγόριθμος DijkstraΕπιχειρησιακή Έρευνα↔ compare
- Ο Αλγόριθμος Ford-FulkersonΕπιχειρησιακή Έρευνα↔ compare
Αναφέρεται από
Εντοπίσατε πρόβλημα σε αυτή τη σελίδα; Αναφέρετέ το ή προτείνετε διόρθωση →