L09 · Γραφήματα IV — Dijkstra & Ελάχιστα Συνδετικά Δέντρα

Τι θα δούμε

Στο L08 είδαμε ότι μόλις οι ακμές αποκτήσουν βάρη, το BFS δεν αρκεί πια. Εδώ φτιάχνουμε τους αλγορίθμους που χρειάζεται — δύο μεγάλα προβλήματα και τέσσερις αλγόριθμοι:

1. Συντομότερη διαδρομή με θετικά βάρη → ο αλγόριθμος Dijkstra.
2. Ελάχιστο Συνδετικό Δέντρο (ΕΣΔ / MST) → Prim, Kruskal, και η «αντίστροφη διαγραφή».

Και οι τέσσερις είναι άπληστοι: σε κάθε βήμα παίρνουν την τοπικά καλύτερη απόφαση και δεν την ξανακοιτάζουν ποτέ. Το ότι μια σειρά από «μυωπικές» επιλογές δίνει στο τέλος παγκόσμια βέλτιστη λύση δεν είναι καθόλου προφανές — η μισή διάλεξη είναι να αποδείξουμε ακριβώς αυτό.

Συντομότερη διαδρομή με βάρη

Είσοδος: κατευθυνόμενο γράφημα $G=(V,A)$, και σε κάθε ακμή $e$ ένας θετικός αριθμός ${\ell }_e>0$ — το «μήκος» της. Το μήκος μιας διαδρομής είναι το άθροισμα των μηκών των ακμών της.

Ζητούμενο: για δοσμένα $s$ και $t$, η διαδρομή $s\to t$ με το ελάχιστο συνολικό μήκος.

Ο αλγόριθμος Dijkstra

Η ιδέα — άπληστο κύμα από την s

Πώς προσομοιώνουμε το κύμα; Κρατάμε ένα σύνολο $S$ από κορυφές που το κύμα έχει ήδη φτάσει — και για τις οποίες ξέρουμε ήδη, οριστικά, τη συντομότερη απόσταση από την $s$. Στην αρχή το κύμα μόλις ξεκινάει: $S=\{s\}$, $d(s)=0$.

Σε κάθε βήμα μεγαλώνουμε το $S$ με μία ακόμα κορυφή — αυτή που το κύμα θα ακουμπήσει αμέσως μετά. Για να τη βρούμε, για κάθε κορυφή $v$ έξω από το $S$ ρωτάμε: «αν την πλησιάσω σε ένα μόνο βήμα από κάποια ήδη οριστικοποιημένη κορυφή $u$, ποιο είναι το φθηνότερο που μου δίνει το $u$;» Αυτό είναι η εκτίμηση $\pi (v)$:

$\pi (v)={\min }_{u\in S,(u,v)\in A}\{d(u)+{\ell }_{u,v}\}$

Η άπληστη επιλογή: παίρνουμε την $v$ με το μικρότερο $\pi (v)$ — αυτή που το κύμα θα ακουμπήσει πρώτη — θέτουμε $d(v):=\pi (v)$, και τη βάζουμε στο $S$. Ποτέ ξανά δεν την ξανακοιτάμε.

Ο αλγόριθμος

Δες τον να τρέχει. Πρόσεξε δύο πράγματα: τη στιγμή που μια κορυφή γίνεται πράσινη (οριστικοποιείται — η απόστασή της δεν θα ξαναλλάξει), και τις στιγμές που ένα $d$ πέφτει όταν βρεθεί φθηνότερη διαδρομή:

Γιατί είναι σωστός — αναλλοίωτη με επαγωγή στο $|S|$

Βάση. $|S|=1$: μόνο η $s$ είναι μέσα, με $d(s)=0$ — προφανώς η συντομότερη διαδρομή προς τον εαυτό της. ✓

Επαγωγικό βήμα. Υποθέτουμε ότι η αναλλοίωτη ισχύει όσο $|S|=k$. Έστω $v$ η κορυφή που μπαίνει στο $S$ στο επόμενο βήμα — αυτή με το ελάχιστο $\pi (\cdot )$ — και έστω $(u,v)$ η ακμή που το πετυχαίνει, ώστε $\pi (v)=d(u)+{\ell }_{u,v}$. Θα δείξουμε ότι καμία διαδρομή $s\to v$ δεν είναι φθηνότερη από $\pi (v)$.

Πάρε λοιπόν μια οποιαδήποτε διαδρομή $P:s\to v$. Καθώς η $P$ ξεκινά μέσα στο $S$ (στην $s$) και καταλήγει έξω (στην $v$), κάποια στιγμή βγαίνει: έστω $(x,y)$ η πρώτη της ακμή με $x\in S$, $y\notin S$, και $P^{\prime }$ το αρχικό κομμάτι $s\to x$. Τότε:

Άρα κάθε διαδρομή προς την $v$ κοστίζει $\ge \pi (v)$, οπότε το $d(v)=\pi (v)$ είναι όντως το συντομότερο. $■$

Η απόδειξη γίνεται πολύ πιο χειροπιαστή αν την τρέξεις. Διάλεξε οποιαδήποτε διαδρομή $s\to v$ και δες την αλυσίδα να χτίζεται κρίκο-κρίκο — και να καταλήγει πάντα στο ίδιο σημείο, $\ge \pi (v)$:

Δεν είναι αφηρημένη απειλή. Ένας τετρακόρυφος γράφος με μία αρνητική ακμή φτάνει για να βάλει τον Dijkstra να επιστρέψει λάθος απάντηση. Πάτα «επόμενο» και δες ακριβώς τη στιγμή που η u «κλειδώνει» στο $d=1$ αν και η αληθινή της απόσταση είναι $-1$ — και πώς αυτό το μικρό ψέμα μετά κάνει την $d[t]$ να είναι 5 αντί για 3:

Από εδώ προκύπτει και ο επόμενος αλγόριθμος, ο Bellman-Ford σε L17: επαναπροσπαθεί τη χαλάρωση κάθε ακμής σε κάθε γύρο, αντί να εμπιστεύεται την «οριστικοποίηση». Πληρώνει με $O(n\cdot m)$ — αλλά αντέχει αρνητικά βάρη και, ως μπόνους, εντοπίζει αρνητικούς κύκλους.

Πολυπλοκότητα

Όλο το κόστος είναι στις δύο πράξεις της ουράς προτεραιότητας:

• $n$ φορές extractMin — μία ανά κορυφή.
• Μέχρι $m$ φορές decreaseKey — το πολύ μία ανά ακμή.

Με έναν δυαδικό σωρό (heap, L10) κάθε πράξη κοστίζει $O(\log n)$, οπότε συνολικά $O((n+m)\log n)=O(m\log n)$ για συνεκτικά γραφήματα. (Με απλό πίνακα αντί σωρού: $O(n^2)$ — προτιμότερο για πυκνά γραφήματα. Με Fibonacci heap: $O(m+n\log n)$, πέρα από την ύλη.)

Ελάχιστο Συνδετικό Δέντρο (ΕΣΔ)

Διατύπωση

Είσοδος: μη κατευθυνόμενο συνεκτικό γράφημα $G=(V,E)$, με κόστος $c_e$ σε κάθε ακμή.

Ένα συνδετικό δέντρο (spanning tree) είναι ένα υποσύνολο ακμών $T\subseteq E$ που (1) είναι δέντρο — συνεκτικό και ακυκλικό — και (2) αγγίζει όλες τις κορυφές. Από το L06, ένα τέτοιο δέντρο έχει ακριβώς $n-1$ ακμές.

Ζητούμενο: το συνδετικό δέντρο ελάχιστου συνολικού κόστους — αυτό που ελαχιστοποιεί το ${\sum }_{e\in T}{c}_e$.

Πού χρησιμεύει στην πράξη: σχεδίαση φθηνότερων δικτύων (ηλεκτρικά, υδρευτικά, καλωδιακά, οδικά)· προσεγγιστικοί αλγόριθμοι για NP-δύσκολα προβλήματα (περιοδεύων πωλητής, δέντρο Steiner)· ανάλυση συστάδων (clustering)· το spanning-tree protocol των Ethernet, που σπάει τους βρόχους ενός δικτύου.

Γιατί δεν δοκιμάζουμε απλώς όλα τα δέντρα

Μια χαζή ιδέα πρώτη: «αν θες ελάχιστο, δοκίμασε τα πάντα — κάθε δυνατό συνδετικό δέντρο — και κράτα το φθηνότερο». Φαίνεται δουλειά υπολογιστή· για ένα γράφημα 10 κορυφών δεν θα μπορούσε να αργήσει τόσο, σωστά;

Το θεώρημα του Cayley σε προσγειώνει: το πλήρες γράφημα $K_n$ έχει $n^{n-2}$ διαφορετικά συνδετικά δέντρα. Δεν είναι «κάποιες δεκάδες» — είναι έκρηξη. Σύρε το $n$ παρακάτω και δες πόσο γρήγορα ο αριθμός σταματάει να χωράει σε χαρτί:

Πέραν του $n\approx 10$, η εξαντλητική απαρίθμηση είναι πρακτικά αδύνατη — δεν προλαβαίνουμε ούτε στα γρηγορότερα μηχανήματα του πλανήτη. Χρειαζόμαστε αλγόριθμο που χτίζει το βέλτιστο δέντρο χωρίς να δει τα υπόλοιπα.

Κύκλοι, αποκοπές, και γιατί η απληστία δουλεύει

Πριν αποδείξουμε ότι Prim και Kruskal είναι σωστοί, χρειαζόμαστε ένα εργαλείο: την έννοια της αποκοπής.

Μια αποκοπή (cut) είναι απλώς ένας χωρισμός των κορυφών σε δύο μέρη — ένα υποσύνολο $A$ και το υπόλοιπο $V\setminus A$. Το σύνολο ακμών αποκοπής $D(A)$ είναι οι ακμές με το ένα άκρο στο $A$ και το άλλο έξω — αυτές που «διασχίζουν» τη γραμμή.

Δες το με τα χέρια σου. Κάνε κλικ στις κορυφές για να φτιάξεις τη δική σου αποκοπή $A$: οι ακμές που τη διασχίζουν — το $D(A)$ — ανάβουν χρυσές, και η φθηνότερη απ' αυτές πρασινίζει. Δοκίμασε όσες διαφορετικές αποκοπές θέλεις και κράτησε μια παρατήρηση για την ελάχιστη χρυσή ακμή — θα της δώσουμε όνομα σε λίγο:

Και ένα λήμμα-εργαλείο — απλό στην απόδειξη, αλλά κάνει το «βρώμικο» επιχείρημα ανταλλαγής που έρχεται μετά να δουλέψει χωρίς τρύπες:

Δοκίμασέ το με τα χέρια σου. Διάλεξε έναν κύκλο, διάλεξε μια αποκοπή, και περπάτησε γύρω-γύρω: ο μετρητής των διασχίσεων ποτέ δεν καταλήγει σε περιττό αριθμό. Όση φαντασία κι αν βάλεις στο πώς θα κόψεις τις κορυφές, ο κύκλος πρέπει να επιστρέψει — και η ισορροπία είσοδος-έξοδος είναι αναπόφευκτη:

Η ιδιότητα αποκοπής

Απόδειξη με ανταλλαγή. Έστω $e$ η ελάχιστη ακμή της αποκοπής, και έστω, για άτοπο, ένα ΕΣΔ $T^{\ast }$ που δεν την περιέχει.

1. Προσθέτοντας την $e$ στο $T^{\ast }$ σχηματίζεται ακριβώς ένας κύκλος $C$ (δέντρο + μία ακμή = ένας κύκλος).
2. Η $e$ ανήκει και στον $C$ και στο $D(A)$. Από το λήμμα κύκλου-αποκοπής, η τομή $C\cap D(A)$ έχει άρτιο πλήθος — άρα υπάρχει και άλλη ακμή $f\ne e$ σε αυτή την τομή.
3. Φτιάξε $T^{\prime }=T^{\ast }\cup \{e\}\setminus \{f\}$. Αφαιρώντας μια ακμή του κύκλου, το $T^{\prime }$ παραμένει συνδετικό δέντρο.
4. Αφού η $e$ είναι η ελάχιστη του $D(A)$ και η $f$ είναι κι αυτή στο $D(A)$, ισχύει $c_e\le c_f$, άρα $\text{cost}(T^{\prime })\le \text{cost}(T^{\ast })$ — και το $T^{\prime }$ περιέχει την $e$. Άρα υπάρχει ΕΣΔ με την $e$. $■$

Η ιδιότητα κύκλου

Απόδειξη — συμμετρική. Έστω $f$ η ακριβότερη ακμή του κύκλου, και έστω, για άτοπο, ένα ΕΣΔ $T^{\ast }$ που την περιέχει.

1. Αφαιρώντας την $f$ από το $T^{\ast }$, το δέντρο σπάει σε δύο κομμάτια — δηλαδή ορίζεται μια αποκοπή $A$.
2. Η $f$ ανήκει και στον $C$ και στο $D(A)$. Από το λήμμα, υπάρχει και άλλη ακμή $e\ne f$ στην τομή $C\cap D(A)$.
3. Φτιάξε $T^{\prime }=T^{\ast }\cup \{e\}\setminus \{f\}$ — η $e$ ξαναενώνει τα δύο κομμάτια, οπότε το $T^{\prime }$ είναι συνδετικό δέντρο.
4. Αφού η $f$ είναι η ακριβότερη του $C$, ισχύει $c_e<c_f$, άρα $\text{cost}(T^{\prime })<\text{cost}(T^{\ast })$ — αντίφαση με το ότι το $T^{\ast }$ ήταν ελάχιστο. $■$

Και οι δύο αποδείξεις είναι, κυριολεκτικά, η ίδια κίνηση: πρόσθεσε ή αφαίρεσε μία ακμή, άφησε το λήμμα κύκλου-αποκοπής να σου δώσει μια δεύτερη ακμή, και κάνε την ανταλλαγή. Δες την να εκτελείται — γύρνα τον διακόπτη ανάμεσα στις δύο ιδιότητες και πρόσεξε πόσο όμοια κινούνται:

Ο αλγόριθμος του Prim

Η ιδέα. Μεγάλωσε ένα δέντρο προς τα έξω. Σε κάθε στιγμή η αποκοπή είναι «κορυφές μέσα στο δέντρο» vs «κορυφές έξω». Από την ιδιότητα αποκοπής, η φθηνότερη ακμή που διασχίζει αυτή τη γραμμή ανήκει σίγουρα στο ΕΣΔ — οπότε την προσθέτουμε, χωρίς δισταγμό.

Δες τον Prim να μεγαλώνει το δέντρο, μία κορυφή τη φορά. Σε κάθε βήμα πρόσεξε την αποκοπή που ορίζει το δέντρο — πράσινο μέσα, λευκό έξω — και τη χρυσή ακμή: τη φθηνότερη που τη διασχίζει, αυτήν ακριβώς που η ιδιότητα αποκοπής εγγυάται πως ανήκει στο ΕΣΔ.

Η διαφορά ακούγεται μικρή ως μια γραμμή σε ψευδοκώδικα — αλλά αλλάζει αυτό που λύνουν οι δύο αλγόριθμοι. Τρέξε τους παράλληλα στο ίδιο γράφημα από την ίδια αφετηρία: συμβαδίζουν μέχρι κάποιο σημείο, ύστερα διαφέρουν, και καταλήγουν σε διαφορετικά δέντρα — γιατί λύνουν διαφορετικά προβλήματα:

Πρόσεξε δύο πράγματα στο τέλος: ο Prim βγάζει δέντρο μικρότερου συνολικού κόστους (όπως πρέπει — είναι ΕΣΔ), αλλά η διαδρομή που σου δίνει το δέντρο του Prim από την αρχή σε κάποιες κορυφές είναι μεγαλύτερη από τη συντομότερη. Ο Dijkstra κάνει το ανάποδο: δεν δίνει ΕΣΔ, αλλά κάθε διαδρομή στο δέντρο του είναι όντως η συντομότερη. Διαφορετικοί στόχοι, διαφορετικά βέλτιστα.

Πολυπλοκότητα: ίδια ανάλυση με τον Dijkstra — $n$ extractMin και μέχρι $m$ decreaseKey, άρα $O(m\log n)$ με σωρό ($O(n^2)$ με απλό πίνακα).

Ο αλγόριθμος του Kruskal

Η ιδέα. Ξέχνα τη γεωμετρία — δούλεψε μόνο με τη λίστα ακμών. Ταξινόμησέ τες σε αύξουσα σειρά κόστους και σάρωσέ τες:

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

Δες τον Kruskal να σαρώνει τις ταξινομημένες ακμές. Κάθε χρώμα είναι ένα ξεχωριστό κομμάτι του δάσους· πρόσεξε δύο κομμάτια να συγχωνεύονται σε ένα μόλις μια ακμή γίνεται δεκτή — και μια ακμή να απορρίπτεται ακριβώς τη στιγμή που θα έκλεινε κύκλο:

Πολυπλοκότητα. Η ταξινόμηση των ακμών κοστίζει $O(m\log m)=O(m\log n)$. Οι $m$ πράξεις Find/Union, με τη δομή Union-Find (union-by-rank + path compression), κοστίζουν $O(m\cdot \alpha (n))$, όπου η $\alpha$ — η αντίστροφη συνάρτηση Ackermann — είναι πρακτικά σταθερά. Άρα κυριαρχεί η ταξινόμηση: $O(m\log n)$.

Μια τρίτη παραλλαγή: αντίστροφη διαγραφή

Λιγότερο γνωστή αλλά πανέμορφη — και αξίζει να την παίξεις τουλάχιστον μία φορά για να σου μπει στο μυαλό η ιδιότητα κύκλου με τη μορφή εργαλείου.

Η ιδέα. Κάνε το ακριβώς αντίθετο του Kruskal. Ξεκίνα με όλες τις ακμές μέσα — δηλαδή με όλο το γράφημα — και σάρωσέ τες σε φθίνουσα σειρά κόστους. Για κάθε ακμή ρώτα: αν την αφαιρέσω, μένει το γράφημα συνεκτικό; Αν ναι, διέγραψέ τη οριστικά. Αλλιώς, ήταν γέφυρα — βάλ' τη πίσω.

Γιατί δουλεύει. Όταν η αφαίρεση δεν αποσυνδέει, σημαίνει ότι υπάρχει εναλλακτική διαδρομή ανάμεσα στα δύο άκρα — δηλαδή η ακμή ήταν μέρος ενός κύκλου. Κι αφού σαρώνουμε από την ακριβότερη προς τη φθηνότερη, η ακμή που εξετάζουμε ήταν η ακριβότερη εκείνου του κύκλου: όλες οι υπόλοιπές του ακμές, που έδιναν την εναλλακτική διαδρομή, ήταν φθηνότερες (αλλιώς θα τις είχαμε ήδη συναντήσει). Η ιδιότητα κύκλου μας εγγυάται ότι αυτή η ακριβότερη ακμή δεν ανήκει σε κανένα ΕΣΔ — άρα δικαιολογημένα τη διώχνουμε για πάντα.

Δες τον αλγόριθμο να σαρώνει και δες την αλλαγή φωνής στη μέση της λίστας: στις 6 ακριβότερες απαντάει «διέγραψε», στις 6 φθηνότερες αρχίζει να απαντάει «κράτησέ τη — γέφυρα». Παρατήρησε επίσης τι μένει στο τέλος — ακριβώς το ΕΣΔ που έβγαλαν και ο Prim και ο Kruskal:

Πολυπλοκότητα: πάλι $O(m\log n)$, αν ο έλεγχος «αποσυνδέεται;» γίνει με κάποια έξυπνη δομή (π.χ. δυναμική συνεκτικότητα). Δεν χρησιμοποιείται συχνά στην πράξη, αλλά είναι το πιο καθαρό παράδειγμα της ιδιότητας κύκλου εν δράσει.

Prim ή Kruskal;

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

Κλείδωσε τη γνώση

Βάλε στη σειρά τα βήματα του Dijkstra:

Και συμπλήρωσε τα κενά για τις δύο ιδιότητες του ΕΣΔ:

Τέλος, βάλε στη σειρά τα βήματα του Kruskal:

Μοτίβο σκέψης