Ανάλυση του Dijkstra PDF

Οι διαφάνειες βασίζονται σε αυτές του ακόλουθου μαθήματος: Introduction to Algorithms (6-046J), MIT https://ocw.mit.edu/courses/electrical- engineering-and-computer-science/6-046j- introduction-to-algorithms-sma-5503-fall-2005/ Οι διαφάνειες του ανωτέρω μαθήματος δίνονται υπό την άδεια «Creative...

Οι διαφάνειες βασίζονται σε αυτές του ακόλουθου μαθήματος: Introduction to Algorithms (6-046J), MIT https://ocw.mit.edu/courses/electrical- engineering-and-computer-science/6-046j- introduction-to-algorithms-sma-5503-fall-2005/ Οι διαφάνειες του ανωτέρω μαθήματος δίνονται υπό την άδεια «Creative Commons Attribution-NonCommercial-ShareAlike 3.0»  Μονοπάτια σε γραφήματα Έστω ένα διγράφημα G = (V, E) με βάρη στις ακμές (w : E R). Το βάρος του μονοπατιού p = v1  v2 … vk ορίζεται ως k 1 w( p)   w(vi , vi1). i1 Παράδειγμα:  Συντομότερα Μονοπάτια Ένα συντομότερο μονοπάτι από το u στο v είναι ένα μονοπάτι ελαχίστου βάρους από το u στο v. Το βάρος του συντομότερου μονοπατιού από το u στο v ορίζεται ως: (u, v) = min{w(p) : p είναι ένα μονοπάτι από το u στο v}. Note: (u, v) =  αν δεν υπάρχει μονοπάτι από το u στο v.  Υποδομή Βέλτιστου Θεώρημα. Ένα υπο-μονοπάτι ενός συντομότερου μονοπατιού είναι επίσης συντομότερο μονοπάτι. Απόδειξη. Αποκοπή και επικόλληση:  Τριγωνική Ανισότητα Θεώρημα. Για όλα τα u, v, x  V, έχουμε (u, v)  (u, x) + (x, v). Απόδειξη.  Αδυναμία εύρεσης συντομότερων διαδρομών Αν ένα γράφημα G περιέχει ένα κύκλο αρνητικού βάρους, τότε κάποια συντομότερα μονοπάτια μπορεί να μην υπάρχουν. Παράδειγμα: Συντομότερα μονοπάτια κοινής αφετηρίας Πρόβλημα. Από μία δοθείσα κορυφή s  V, βρες τα βάρη των συντομότερων μονοπατιών (s, v) για όλα τα v  V. Αν όλα τα βάρη των ακμών w(u, v) είναι μη αρνητικά, όλα τα βάρη των συντομότερων μονοπατιών πρέπει να υπάρχουν. ΙΔΕΑ: Άπληστος Αλγόριθμος. 1. Διατήρησε ένα σύνολο S κορυφών των οποίων οι συντομότερες αποστάσεις από το s είναι ήδη γνωστές. 2. Σε κάθε βήμα, πρόσθεσε στο S την κορυφή v  V – S της οποίας η εκτίμηση της απόστασης από τη s είναι ελάχιστη. 3. Ενημέρωσε τις εκτιμήσεις αποστάσεων κορυφών που είναι γειτονικές με τη v.  Αλγόριθμος Dijkstra d[s]  0 for each v  V – {s} do d[v]   S   QV ⊳ Q is a priority queue maintaining V – S while Q   do u  EXTRACT-MIN(Q) S  S  {u} for each v  Adj[u] do if d[v] > d[u] + w(u, v) Βήμα then d[v]  d[u] + w(u, v) Χαλάρωσης DECREASE-KEY  Παράδειγμα 2 Γράφημα με B D μη αρνητικά 10 βάρη ακμών A 1 4 8 7 9 3 C 2 E  Παράδειγμα Αρχικοποίηση:   2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0       S: {}  Παράδειγμα   “A”  EXTRACT-MIN(Q): 2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0       S: { A }  Παράδειγμα Χαλάρωσε όλες τις ακμές 10  2 που εξέρχονται της A: B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3  10    S: { A }  Παράδειγμα 10  “C”  EXTRACT-MIN(Q): 2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3  10    S: { A, C }  Παράδειγμα 7 11 Χαλάρωσε όλες τις ακμές 2 που εξέρχονται της C: B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3 5 10    7 11 5 S: { A, C }  Παράδειγμα 7 11 “E”  EXTRACT-MIN(Q): 2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3 5 10    7 11 5 S: { A, C, E }  Παράδειγμα Χαλάρωσε όλες τις ακμές 7 11 που εξέρχονται της E: 2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3 5 10    7 11 5 7 11 S: { A, C, E }  Παράδειγμα 7 11 “B”  EXTRACT-MIN(Q): 2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3 5 10    7 11 5 7 11 S: { A, C, E, B }  Παράδειγμα Χαλάρωσε όλες τις ακμές 7 9 που εξέρχονται της B: 2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3 5 10    7 11 5 7 11 S: { A, C, E, B } 9  Παράδειγμα 7 9 “D”  EXTRACT-MIN(Q): 2 B D 10 8 0 A 1 4 7 9 3 Q: A B C D E C 2 E 0     3 5 10    7 11 5 7 11 S: { A, C, E, B, D } 9 Χαλάρωση ακμής  Ορθότητα — Μέρος I Λήμμα. Με αρχικές τιμές d[s]  0 and d[v]   για όλα τα v  V – {s}, ισχύει d[v]  (s, v) για όλα τα v  V, και αυτή η αναλλοίωτη συνθήκη διατηρείται με οποιαδήποτε ακολουθία βημάτων χαλάρωσης. Απόδειξη. Υποθέτουμε το αντίθετο. Αν v η πρώτη κορυφή για την οποία d[v] < (s, v), και έστω u η κορυφή που προκάλεσε την αλλαγή της d[v] : d[v] = d[u] + w(u, v). Τότε, d[v] < (s, v) Υπόθεση  (s, u) + (u, v) Τριγωνική ανισότητα  (s,u) + w(u, v) συν. μον.  συγκεκρ. μον.  d[u] + w(u, v) v είναι η πρώτη παραβίαση Άτοπο.  Ορθότητα — Μέρος II Λήμμα. Έστω u ο προηγούμενος του v κόμβος στο συντομότερο μονοπάτι από το s στο v. Τότε, αν d[u] = (s, u) και η ακμή (u, v) υφίσταται χαλάρωση, έχουμε d[v]  (s, v) μετά τη χαλάρωση. Απόδειξη. Παρατηρείστε ότι (s, v) = (s, u) + w(u, v). Υποθέστε ότι d[v] > (s, v) πριν τη χαλάρωση. (Αλλιώς, έχουμε τελειώσει.) Τότε, ο έλεγχος d[v] > d[u] + w(u, v) επιτυγχάνει, διότι d[v] > (s, v) =(s, u) + w(u, v) = d[u] + w(u, v), και ο αλγόριθμος θέτει d[v] = d[u] + w(u, v) = (s, v).  Ορθότητα — Μέρος III Θεώρημα. Ο αλγόριθμος του Dijkstra τερματίζει με d[v] = (s, v) για όλα τα v  V. Απόδειξη. Αρκεί να δείξουμε ότι d[v] = (s, v) για κάθε v  V όταν το v προστίθεται στο S. Υποθέστε u είναι η πρώτη κορυφή που προστίθεται στο S για την οποία d[u]  (s, u). Αν y είναι η πρώτη κορυφή στο V – S στο συντομότερο μονοπάτι από το s στο u, και έστω x η προηγούμενη του κορυφή: u s S, ακριβώς πριν x y την πρόσθεση του u.  Ορθότητα — Μέρος III (συν.) S u s x y Αφού u είναι η πρώτη κορυφή που παραβιάζει την αναλλοίωτη συνθήκη, έχουμε d[x] = (s, x). Όταν η x προστίθεται στο S, η ακμή (x, y) υφίσταται χαλάρωση, το οποίο συνεπάγεται ότι d[y] = (s, y)  (s, u)  d[u]. Αλλά, d[u]  d[y] από την επιλογή του u. Άτοπο. Ανάλυση του Dijkstra while Q   do u  EXTRACT-MIN(Q) S  S  {u} for each v  Adj[u] do if d[v] > d[u] + w(u, v) then d[v]  d[u] + w(u, v)  Analysis of Dijkstra while Q   do u  EXTRACT-MIN(Q) |V | S  S  {u} φορές for each v  Adj[u] do if d[v] > d[u] + w(u, v) then d[v]  d[u] + w(u, v)  Ανάλυση του Dijkstra while Q   do u  EXTRACT-MIN(Q) |V | S  S  {u} φορές for each v  Adj[u] degree(u) do if d[v] > d[u] + w(u, v) φορές then d[v]  d[u] + w(u, v)  Ανάλυση του Dijkstra while Q   do u  EXTRACT-MIN(Q) |V | S  S  {u} φορές for each v  Adj[u] degree(u) do if d[v] > d[u] + w(u, v) φορές then d[v]  d[u] + w(u, v) (E) DECREASE-KEY’s.  Ανάλυση του Dijkstra while Q   do u  EXTRACT-MIN(Q) |V | S  S  {u} φορές for each v  Adj[u] degree(u) do if d[v] > d[u] + w(u, v) φορές then d[v]  d[u] + w(u, v)    (E) implicit DECREASE-KEY’s. Χρόνος = (V·TEXTRACT-MIN + E·TDECREASE-KEY) Σημείωση: Ο ίδιος τύπος όπως στην ανάλυση του αλγορίθμου του Prim.  Ανάλυση του Dijkstra Time = (V)·TEXTRACT-MIN + (E)·TDECREASE-KEY Q TEXTRACT-MIN TDECREASE-KEY Σύνολο πίνακας O(V) O(1) O(V2) Δυαδικός O(E lg V) O(lg V) O(lg V) σωρός Fibonacci O(lg V) O(1) O(E + V lg V) σωρός amortized amortized Χειρότερη περίπτωση