[SCRÂȘIT] [FOSȘIT] [CLIC] JASON KU: Bună dimineața tuturor. Bun venit la a 13-a prelegere din 6.006. Pentru a recapitula data trecută, în ultimele două prelegeri am vorbit despre cele mai scurte – cele mai scurte căi de o singură sursă pe grafice ponderate . Anterior vorbeam doar despre grafice neponderate. Și până acum, până astăzi, am vorbit despre trei moduri de a rezolva cele mai scurte căi cu o singură sursă pe grafice ponderate. Și anume primul a folosit BFS. Dacă vă puteți transforma într-un fel graficul într-un grafic de dimensiune liniară, care este neponderat, care corespunde problemei dvs. ponderate , înlocuind în esență fiecare muchie ponderată cu greutate w cu w muchii unice. Acum, asta este bun numai pentru lucruri pozitive cu greutate și dacă suma greutăților tale este mică. Dar dacă suma greutăților tale este liniară în dimensiunea combinatorie a graficului tău, V plus E, atunci putem obține un algoritm de timp liniar pentru a rezolva cele mai scurte căi ponderate folosind căutarea pe lățimea întâi. Apoi am vorbit despre cum am putea-- dacă am-- problema cu cele mai scurte căi ponderate este dacă greutățile noastre ar fi negative și ar putea exista cicluri, atunci am putea avea cicluri negative de greutate și asta ar fi mai dificil de gestionat, pentru că atunci au vârfuri în care aveți un număr nemărginit de muchii pe care s-ar putea să trebuiască să le parcurgeți pentru o cale mai scurtă. S- ar putea să nu existe o cale mai scurtă cu lungime finită. Dar în condiția în care nu aveam cicluri în grafic -- desigur, nu puteam avea cele cu greutate negativă, așa că am putut face asta și în timp liniar exploatând faptul că vârfurile noastre ar putea fi ordonate în o ordine topologică și apoi am putea împinge informațiile despre calea cea mai scurtă de la cea mai îndepărtată înapoi la cele înainte. Prin relaxarea marginilor înainte. Menținând acest invariant, am avut cele mai scurte căi pe măsură ce procesam aceste lucruri în ordine topologică. Apoi, data trecută, vorbeam despre grafice generale, grafice care ar putea conține cicluri, iar acesta este algoritmul nostru cel mai general , pentru că dacă există cicluri de greutate negative, Bellman-Ford, despre care am vorbit data trecută, le poate detecta. Și, în special, pentru orice vârf care a avut o greutate finită calea cea mai scurtă - calea, am putea calcula acea cale cea mai scurtă pentru el, să-i calculăm distanța. Și pentru orice persoană accesibilă dintr-un ciclu de pondere negativă , nu numai că l-am putea marca ca minus distanța infinită, dar am putea găsi, de asemenea, un ciclu de pondere negativă, în esență, duplicând graficul nostru pentru a-l face un DAG și a putea urmări indicatorii înapoi. în acest DAG extins care avea mai multe straturi. Deci asta am făcut până acum. Am devenit liniari pentru unele tipuri de grafice. Și am obținut un fel de V pătratic ori E pentru graficele generale, cele care ar putea conține cicluri negative. Acum cât de rău este asta? Ei bine, dacă graficul este rar, dacă numărul de muchii din graficul nostru este de ordinul lui V, atunci acesta este timp pătratic și V, V pătrat. Dar dacă graficul este dens acolo unde avem pătratice-- ca și graficul complet în care fiecare muchie este prezentă, atunci avem în graficul nostru multe muchii pătratice în V. Și astfel acest timp de rulare este V cubit. V cube nu este grozav în ceea ce privește timpul de funcționare. Ne- am dori ceva mai aproape de liniar. Și așa vom face astăzi. Dacă avem această restricție în care avem greutăți nenegative, putem avea cicluri de greutate negative. Și aceasta este o restricție care apare mult pentru multe grafice pe care le puteți întâlni. De multe ori nu ai atât greutatea pozitivă, cât și cea negativă . Nu am o distanță negativă până la casa mea. În orice metrică avem ponderi nenegative. Așa că aceste lucruri apar foarte mult și ne putem descurca mult mai bine, deoarece nu există cicluri negative de greutate , putem deveni aproape liniari. Nu va fi chiar V plus E, așa cum vedeți aici sus pe diapozitiv. Vom ajunge la ceva foarte aproape. Este V plus E, dar pe termenul V, avem acest factor logaritmic în V. Care ne amintim, pentru toate intențiile și scopurile, acest jurnal al aceluiași lucru în viața reală nu va fi mai mare decât un factor de 30 sau ceva de genul. ca asta. Poate 60. Dar este un număr mic. Și deci aceasta este de fapt o performanță destul de bună. Este aproape liniar - asta spun eu aici aproape liniar, și asta vom încerca să facem astăzi. Deci, cum facem asta? Ei bine, voi face două observații aici, în primul rând. Ideea noastră va fi să generalizăm noțiunea de BFS. Când am avut BFS, ne-am împărțit graficul -- pentru a rezolva neponderate -- pentru a rezolva cele mai scurte căi ponderate în BFS, am putea lua ponderile noastre pozitive, le-am împărți în muchii individuale. Dar dacă greutatea totală a marginilor noastre ar fi mare, atunci am avea o problemă, pentru că acum am extins dimensiunea graficului nostru. Aceasta este aceeași problemă pe care am avut-o cu ceva de genul radix sort, unde nu vrem ca algoritmul nostru să ruleze în dimensiunea numerelor din intrarea noastră, vrem ca algoritmul nostru să ruleze în numărul de numere din intrarea noastră. Aceasta este diferența dintre N și U atunci când vorbeam despre structurile de date. Aici, dacă dimensiunea greutăților noastre este mare în comparație cu V și E, atunci realizarea acestei expansiuni va fi dificilă. Dar dacă am avea, să zicem, un grafic - acesta este graficul meu G și am avut un vârf s sursă , ideea aici va fi totuși să încercăm să creștem o frontieră de distanță crescândă față de sursa mea și să încerc să menținem toate a lucrurilor aflate la o anumită distanță de sursa mea. Deci asta e ideea, să crești o sferă centrată la sursa mea, să explorez în mod repetat vârfuri mai apropiate înainte de a ajunge la altele mai departe. Dar cum pot explora vârfuri mai apropiate dacă nu cunosc distanțele în prealabil? Aceasta este un fel de-- pare o logică circulară. Voi folosi distanța până la lucrurile mele pentru a calcula distanța până la lucrurile mele. Asta nu funcționează atât de bine. Deci, cum facem asta? Ei bine, ideea aici este să calculăm treptat distanțele-- să calculăm distanțele pe măsură ce mergem, astfel încât să menținem această proprietate. Acum această proprietate, această idee nu ar funcționa neapărat în contextul greutăților marginilor negative. Aici, avem această frontieră în creștere, această minge în jurul sursei mele. Și pe măsură ce îmi cresc lucrurile, aceste lucruri se află la o distanță din ce în ce mai mare, pentru că orice margine de la ceva de aici, pe măsură ce îmi cresc mingea la o anumită distanță, aceste lucruri sunt în afara acelei distanțe. Aici folosim o observație cheie. Iată observația mea 1. Dacă greutățile sunt mai mari sau egale cu 0, atunci distanțele cresc pe cele mai scurte căi. Poate crește slab monoton dacă există margini cu greutate zero. Dar, în general, dacă am avut o cale care merge de la s la vreo v și trece printr-un vârf u, am cea mai scurtă cale. Aceasta este calea cea mai scurtă de la s la v și trece printr-un punct u, un vârf u. Apoi, această monotonitate înseamnă mai precis că cea mai scurtă cale de la s la u și cea mai scurtă cale de la s la v, care este toată chestia asta, cum se leagă acestea între ele? Dacă aceasta se află de-a lungul acelei căi, atunci aceasta trebuie să fie cel puțin la fel de mare ca și calea secundară. Pentru că toate acestea... greutatea acestei căi nu poate fi negativă. Deci ăsta e lucrul pe care Dijkstra îl va exploata. În esență înseamnă că, atunci când extind această frontieră de distanță de la x, este posibil dacă aș avea pondere negativă, că această linie-- dacă aș avea o pondere foarte negativă care merge de la un vârf de aici la un vârf de aici, acest vârf ar putea fi în această limită. Poate dacă această distanță este x, acest tip ar putea fi în limita x. Lucrurile care se află la distanța x din s ar putea să nu fie toate conținute. Ar putea exista o cale de aici până la această altă distanță de lățime a vârfurilor x. Nu are această proprietate pentru că aș putea scădea distanța de-a lungul potecii. Deci aceasta este prima observație. A doua observație, ei bine, să vedem dacă ne putem ajuta la relaxarea DAG. Vă pretind că putem rezolva mai repede căile cele mai scurte cu o singură sursă dacă ni se oferă în prealabil o ordine de vârfuri în distanță crescătoare. Distanța de la s. Deci iată ideea. Nu am de gând să vă dau distanțele până la toate aceste vârfuri. În schimb, am să vă dau ordinea vârfurilor la o distanță crescândă de la s. Deci, practic, spun, dacă aș avea ceva, nu știu, iată un grafic. Să vedem dacă îmi amintesc. OK, și voi pune niște margini aici. BINE. Și voi numi aceste vârfuri 0, 1, 2, 3 și 4. OK. Deci iată un grafic. Poate am pus niște greutăți de margine aici. Voi spune că acesta este 3, acesta este 2, acesta este 3, acesta este 1, acesta este 1 , acesta este 0 și acesta este 0. Deci, de la vârful 1 la 2, acesta a fost 2 pentru etichetarea acelui vârf. Acea margine are greutate zero. BINE. Deci, iată un grafic ponderat și nu știu neapărat... Aș putea folosi Bellman-Ford pentru a găsi cele mai scurte căi de la acest vârf 0, dar ideea aici este că nu vă voi oferi cele mai scurte căi, o să încercați să calculez cele mai scurte căi, dar vă voi oferi câteva informații suplimentare. O să vă dau ordinea distanței celei mai scurte ale lor de la sursă. Și pot doar... O să mă uit la asta și să spun... O să schimb puțin asta pentru a o face puțin mai interesantă. O să spun că aceasta este distanța 4. OK. Bine, deci acum avem cea mai scurtă distanță de cale... Mă uit la asta. Cea mai scurtă distanță până la... exemplu prost. În regulă. Deci, acestea sunt greutățile. Cea mai scurtă distanță până la 3 va fi 2, voi spune, prin acolo. Distanța pe calea cea mai scurtă aici este de asemenea 2. Distanța pe calea cea mai scurtă aici este, de asemenea, 2, deoarece pot trece prin ambele 0 și nu este o problemă. Și apoi cea mai scurtă distanță de aici este 2 până aici și 1/3 până acolo. Deci acestea sunt listate la distanță tot mai mare de la sursa mea. A trebuit să calculez acele delte pentru a vă convinge că aceasta a fost ordonarea corectă, dar aceasta este o ordonare corectă a acestor lucruri. Acum nu este singura comandă corectă, dar este o comandă corectă. OK, așa că mi s-a spus-- Vă argumentez că aș putea rezolva o singură sursă cele mai scurte căi în timp liniar dacă v-aș da vârfurile la distanță crescândă? Cum as putea sa fac asta? Ei bine, din cauza acestei prime observații, știu că dacă acestea cresc în distanță, orice margine care merge înapoi în raport cu această ordonare nu poate participa la cele mai scurte căi cu o singură excepție. Știe cineva care este această excepție? Nicio margine nu poate merge înapoi în această ordonare bazată pe această observație decât în ​​ce condiție? Da? PUBLIC: Dacă greutatea este 0? JASON KU: Dacă greutatea la 0, da. Deci, dacă greutatea la 0, la fel ca această situație aici, atunci aș putea merge înapoi în comanda. Vezi, e problematic. Ideea este că voi dori să construiesc un DAG, astfel încât să pot rula relaxarea DAG. Ei bine, dacă am o componentă aici care are 0 greutăți, pot uni chestia asta în jos-- Pot să mă ocup de această componentă separat. Să ne facem griji despre asta separat. Dacă o facem, putem restrânge această muchie într-un singur vârf și transforma acest grafic astfel încât să respecte ordinea. Așa că voi transforma acest grafic într-un nou grafic. Acesta este un grafic-- conține vârful 2 și vârful 0, vârful 1 și 3 aici și vârful 4. OK, acum avem... și voi păstra doar marginile înainte în... trebuie să restrângeți întreaga secțiune într-un singur vârf. Acest lucru nu prea funcționează. BINE. Să ignorăm marginile cu greutate zero pentru moment. Să presupunem că acestea sunt... în regulă, e ceva rupt aici. Dacă am un ciclu aici... chiar acum nu am un ciclu de greutate zero. Deci, ceea ce aș putea face este să iau acest vârf și să-l pun după ambele vârfuri. Și acum aș-- sau aș putea rearanja ordinea acestor trei vârfuri unde există o cale de lungime 0 și aș obține o nouă ordonare care încă satisface proprietatea. Și acesta este întotdeauna cazul, deoarece căile nu pot crește - căile nu pot scădea în greutate. Pot rearanja ordonarea acestor lucruri astfel încât 3 să fie primul, 1 să fie al doilea și 2 să fie al treilea dintre cele trei vârfuri. Da. Deci, pentru fiecare set de 0 muchii, pot doar să răsturn relația dacă au aceeași distanță. În intrarea mea, mi se oferă vârfuri care au aceeași distanță de sursă. Și așadar, dacă acestea sunt la aceeași distanță de sursă și sunt conectate printr-o margine de greutate zero, nu mă strica să le schimb comanda. Așa că o să fac asta. Deci, să transformăm asta într-un grafic cu o ordine diferită. 0 3 acum, 1 2. OK și am această distanță, această margine, această margine, această margine, această margine. Această margine. Ce îmi lipsește? 2 la 3. Și aici. Cred că am toate aceste margini. Da? BINE. Acum am proprietatea că fiecare margine care ar putea participa la calea cea mai scurtă merge înainte în comanda, deoarece toate acestea sunt de greutate zero. Așa că le întoarcem astfel încât să meargă corect în ceea ce privește comanda. Și orice margine care merge înapoi, care este o greutate pozitivă, cu siguranță nu poate fi folosită pe calea cea mai scurtă. Așa că am de gând să scap de ele. Da? Ce fac dacă există un ciclu de greutate zero? JASON KU: Dacă există un ciclu cu greutate zero, le pot uni pe toate până la un singur vârf, pentru că dacă ajung la unul dintre ele, le pot atinge pe toate. PUBLIC: Primești o ordonare topologică a... JASON KU: Exact. Eu calculez, așa că ideea aici este că încercăm să construim un DAG. Pot construi acest DAG în timp liniar. Și apoi pot rula relaxarea DAG pe acest grafic în timp liniar pentru a obține cele mai scurte căi. Deci asta este o abordare. Dacă aș ști ordonarea vârfurilor în distanță crescătoare, atunci aș putea folosi relaxarea DAG. Deci vom folosi ambele observații. Așa vom rezolva această problemă a lipsei unei singure surse cu ponderi nenegative folosind Dijkstra. Deci, în sfârșit, aici ajungem. Îmi pare rău, am omis un caz aici când îmi scriam notele și am încercat să-l repar live și sper că m-ați urmărit. BINE. algoritmul lui Dijkstra. Am scris corect? Cam. BINE. Ce? Dijkstra. BINE. Acum, Dijkstra era acest informatician olandez. Acesta este el. Destul de faimos, el a scris o monografie despre de ce limbajele de programare ar trebui să înceapă cu indexarea 0 spre deosebire de indexarea 1, așa că îmi place de el. Dar, în special, a proiectat această generalizare foarte frumoasă a BFS pentru grafice ponderate. Dar poate că nu am scris corect, pentru că atunci când își scrie numele, îl scrie cu un Y cu liniuță deasupra. Deci, în realitate, pe o mașină de scris olandeză, s- ar putea să ai un personaj care arată așa, Y cu un umlaut deasupra. Dar pe modern-- pe o tastatură engleză, aceasta arată destul de asemănătoare cu un IJ. Deci, în multe manuscrise, îl scriem ca D-I-- nu există niciun sunet J în Dijkstra. Vine de aici este Y aici. Acesta este un mod interesant de a vă aminti cum să scrieți Dijkstra. Dar ideea de bază din spatele lui Dijkstra este următoarea idee. Margini relaxate de la vârfuri la distanță crescândă de la sursă. BINE. Acesta este același tip de dificultate pe care l-am avut înainte când încercam să generalizăm BFS. Deci, cum știm care este următorul vârf cu distanța în creștere la s? Ei bine, a doua idee este să găsiți următorul vârf în mod eficient folosind o structură de date. Și structura de date pe care o vom folosi este ceva ce îmi place să numesc o coadă de prioritate schimbabilă. Deci, aceasta este puțin diferită de o coadă de prioritate normală pe care o aveam la sfârșitul unității noastre de structuri de date. Această coadă de prioritate modificabilă are trei operații. Vom spune că este o coadă. Îl putem construi pe un set iterabil de articole. Pune doar x-- ca n articole acolo. Putem șterge min din coadă. OK, aceasta este aceeași acum cu coada de prioritate. Aceasta a treia operație va fi diferită. Reduceți cheia unui element care are id, id. Bine, deci este puțin ciudat. Ce naiba este acest id? În regulă, cu o schimbare a cozii de prioritate, fiecare dintre articolele noastre are două valori în loc de o singură valoare. Are o cheie, dar și-- pe care coada de prioritate conduce elementul minim cu cheia minimă. Dar, de asemenea, fiecare articol are asociat un ID , un întreg unic. Astfel încât atunci când efectuăm această operație, reduce_key, poate găsi un element în structura noastră de date cu ID-ul dat. Și dacă este conținut acolo, își va schimba cheia cu o valoare mai mică k. Și nu vă faceți griji pentru cazurile marginale de aici. Ne vom asigura întotdeauna că acest k va fi mai mic decât orice ar fi acea cheie la început. Deci aceasta este într-adevăr un fel de operațiune funky. Dacă am avut o coadă de prioritate, nu o coadă de prioritate modificabilă, dar am avut o coadă de prioritate și aș fi vrut să implementez o schimbare a coadei de prioritate, cum aș putea face acest lucru? Ei bine, o coadă de prioritate obișnuită îmi va aduce deja aceste două operațiuni. Este doar acesta. În esență, trebuie să găsesc ceva după un ID și apoi să-i actualizez cheia. Deci, ideea cum să implementați acest lucru va fi să folosiți o coadă de prioritate obișnuită. Îi voi numi Q prime. Și o să-l încrucișez cu un dicționar D. Deci acestea sunt doar o coadă de prioritate obișnuită pentru articolele mele care are cheia așa cum este definită mai sus. Dar îl voi face legătura încrucișată cu un dicționar, un dicționar care mapează ID-urile la locația lor în coada de prioritate. Am făcut acest lucru de multe ori în secțiunea structuri de date. Încercăm să facem legătura încrucișată cu structurile de date pentru a face o interogare pe un alt tip de cheie pentru a-și găsi locul într-o altă structură de date. Deci, dacă am avea prioritate un dicționar, am putea face aceste lucruri destul de repede. În special, voi presupune că ID-urile noștri ale vârfurilor noastre sunt numere întregi între 0 și v minus 1. Și astfel, pentru dicționarul meu, aș putea obține timp constant să caut acel ID folosind ce structură de date? PUBLIC: Tabel hash. JASON KU: Am putea obține... OK, așa că am putea obține timpul constant așteptat dacă am folosi o tabelă hash. Dar dacă am ști că ID-urile noștri noștri sunt doar numerele de la 0 la v minus 1, am putea scăpa de acel timp așteptat folosind o matrice de acces direct. Grozav. OK, deci asta e presupunerea. Și deci într-adevăr, numele jocului aici este să alegem o coadă de prioritate aici, care va face aceste lucruri mai repede atunci când începem să ne uităm la Dijkstra. OK, așa că vom folosi această structură de date pentru a ține evidența estimărilor noastre de distanță la toate nodurile aflate la distanță de s. OK, deci acesta este algoritmul lui Dijkstra. BINE. Set-- deci același pas de inițializare. Vom stabili... aceasta este o distanță estimată d, nu delta. Vom dori ca d să fie delta noastră la sfârșitul algoritmului. Asta va trebui să dovedim. Așa că le setăm mai întâi pe toate la infinit și apoi setăm d de s, s egal cu 0. Și aici, nu o vom mai actualiza niciodată, deoarece distanța noastră cea mai scurtă este într-un grafic cu greutăți de margine nenegative, cu siguranță nu pot coborî sub 0. Bine. Acum ne construim-- construim coada noastră de priorități schimbătoare-- coada-- cu un articol-- Voi spune că un articol este-- x este reprezentat de un tuplu al ID-ului său, iar apoi cheia sa doar pentru concizie aici . Cu un element v, d din s, v. Deci voi stoca în coada mea de prioritate modificabilă eticheta vârfului și estimarea distanței sale pe calea cea mai scurtă d. Și asta va fi cheia, minimul pe care încerc să îl întreb pentru fiecare v și V. Așa că voi construi acel lucru. Apoi va avea toate nodurile mele în graficul meu. Apoi, în timp ce coada mea de prioritate modificabilă încă mai are articole, nu goale, voi șterge unele u, d s, u. Deci un element astfel încât distanța sa este minimizată de la Q care are distanța minimă. BINE. Așa că mă voi uita la toate lucrurile din coada mea de prioritate. La început, va fi doar s, pentru că totul ca distanță pe calea cea mai scurtă estimare infinită, cu excepția s. Și deci acesta este clar cel mai mic. OK, așa că o voi elimina din coada mea de așteptare și apoi o voi procesa. Cum o voi procesa? Este exact același fel ca și relaxarea DAG. O să-i relaxez toate marginile de ieșire. Așa că doar pentru completitudine pentru v în adiacențele de ieșire ale lui u, mă voi relaxa... îmi pare rău. Trebuie să verificăm dacă ne putem relaxa. Practic, dacă distanța pe calea cea mai scurtă estimată la v este mai mare decât a merge mai întâi la u și apoi a traversa acea margine, dacă trecerea prin aceasta este mai bună, aceasta încalcă inegalitatea noastră de triunghi. Și așa ne relaxăm marginea u, v și prin asta ne referim la setați acest lucru să fie egal cu acel lucru. Asta am vrut să înțelegem prin relaxare. Și apoi mai avem un lucru de făcut. Am schimbat aceste estimări ale distanței, dar Q-ul nostru nu știe că schimbăm aceste lucruri. Am adăugat aceste articole aici. Dar nu știe că distanțele mele s-au schimbat. Așa că îi spunem lui Q să-și amintească să-și schimbe valoarea cheie asociată cu elementul v. Deci, scădeți-- ce este? Descreșteți vârful cheie v în Q la noul d s, v, cel pe care tocmai l-am scăzut aici. Și știu că am scăzut pentru că am spus-o la o valoare mai mică. Are sens. Bine, deci acesta este Dijkstra. Să-l rulăm pe un exemplu. Deci iată un exemplu. Am un grafic dirijat. Conține cicluri. În special, iată câteva cicluri. Cred că acestea sunt principalele. Cu siguranță există cicluri în acest grafic. Dar, după cum vedeți, toate ponderile sunt nenegative, în special, sunt pozitive, de fapt. Va fi doar util să scrieți acest exemplu. Deci, să rulăm Dijkstra pe acest grafic. Mai întâi inițializam și setăm distanța pe calea cea mai scurtă. Îl voi eticheta în alb aici pentru toate lucrurile. Apoi, pe măsură ce îl actualizez, o să le sting și o să scriu un număr nou. Deci asta este la început. Aceasta este inițializarea, aceasta este după pasul 1. Și apoi bag lucrurile în Q-ul meu. Ce este în Q-ul meu? Iată Q-ul meu. Este totul. Sunt vârfurile s, a, b, c, d. Am cinci articole în Q. Într-adevăr, este perechea de articole cu cea mai scurtă distanță estimată, pur și simplu nu o voi rescrie aici. Deci ideea aici este... bucla while, OK. Q nu este gol, grozav. O vom șterge pe cea cu cea mai mică distanță estimată, care este s, corect, da. Așa că elimin asta și apoi relaxez marginile din s. Așa că mă relaxez aici la a. Aceasta este mai bună decât distanța estimată - 10 este mai bună decât distanța estimată infinită, așa că o voi schimba la 10. Și apoi iată o altă margine de ieșire. 3 este mai bun decât infinit, așa că îi voi schimba delta la 3. OK. Așa că acum mă întorc aici și schimb estimările distanței asociate cu Q-ul meu. Acum, următorul pas al algoritmului, s este gata. Am procesat totul la distanță 0. Dar acum voi folosi coada mea de prioritate pentru a spune care dintre vârfurile mele are cea mai scurtă distanță estimată acum. Deci care este? a, b sau c sau d? Da, este 3 și c. 3 este mai mic decât 10. Deci Q va șterge magic c pentru mine, spune-mi ce este, iar acum o voi procesa. Acum mi-am schimbat limita la asta. Și acum relaxez marginile din c. Deci iată o margine la un c, adică un 4. Un 4 plus 3 este mai mic decât 10, așa că îl actualizez. 3 plus 8 este 11, asta e mai mic decat infinit, asa ca il actualizez, ma relaxez. 3 plus 2 este mai mic decât infinit, așa că mă relaxez și la asta. Acum, dintre lucrurile rămase în Q-ul meu, de fapt îl voi elimina de pe Q-ul meu în loc să-l trimit , poate că este mai bine. Dintre vârfurile rămase în Q-ul meu , care are distanța cea mai mică? Da. d. d are 5, 7 sau 11. 5 este cel mai mic. Așa că scot d ​​din tac și relaxez marginile de pe el. Și acum granița mea arată cam așa. Îmi relaxez marginile. 5 plus 5, adică 10. 10 este mai mic decât 11, deci este un 10. Și acesta este singurul avantaj de ieșire din d. asa ca am terminat. Și apoi ultimul, 7 este mai mic decât 10, relaxez marginile din a. a la b, 7 plus 2 este mai mic decât 10. Și acum am terminat. Deci, ceea ce am făcut de fiecare dată când am eliminat s-- sau am eliminat un vârf, i-am spus distanța cea mai scurtă de cale până la small-- ultima valoare pe care i-am atribuit-o. Deci acesta a fost atunci 3, și apoi a a fost 7, b a fost 9 și apoi d a fost 5. Deci, acesta este Dijkstra în acțiune. Se pare că acestea sunt cele mai scurte distanțe, dar cum dovedim asta? A făcut ceea ce trebuie? Ei bine, hai să aflăm. Deci, pentru asta vom petrece ceva timp acum, doar vorbind despre corectitudinea algoritmului lui Dijkstra. BINE. Corectitudinea rezultă din două observații principale. Așadar, afirmația aici pe care încercăm să o dovedim este că d din s este egal cu delta s-- deci estimările egale cu distanța pe calea cea mai scurtă se află la sfârșitul lui Dijkstra pentru toate v și V la sfârșit. Și acest lucru va decurge din două observații. Deci, dovada aici, în primul rând, dacă relaxarea stabilește vreodată d de s din v-- stabilește estimarea egală cu distanța pe calea cea mai scurtă, dacă face vreodată asta, vă argumentez că încă este adevărat la sfârșit. OK, nu este o afirmație foarte puternică. Aceasta înseamnă că dacă am setat vreodată distanța estimată la distanța reală, nu o voi seta niciodată la o valoare diferită mai târziu. De ce, mă rog? Ei bine, relaxarea nu face decât să reducă distanța. Relaxarea scade doar d s, v. Dar am demonstrat în prelegerea 11 -- deci acum două prelegeri că relaxarea este sigură. Și ce înseamnă sigur? Sigur înseamnă că relaxarea-- că relaxarea va schimba vreodată aceste estimări îndepărtate pentru a fi fie infinite-- nu a fost niciodată-- nu a existat niciodată o cale către vârful meu. Sau era lungimea unei căi până la v. Lungimea unei căi. BINE. Deci ce înseamnă asta? Descrește doar, dar este întotdeauna lungimea unei căi către v. Deci, dacă aceasta este lungimea celei mai scurte căi către v, nu aș putea niciodată să o setez la o lungime mai mică, deoarece nu există căi cu distanță mai mică. Asta e toată ideea. BINE. Deci, cu această observație, voi argumenta această afirmație finală. Este suficient să arăt că estimarea mea este egală cu cea mai scurtă distanță atunci când v este îndepărtat din Q. Și din moment ce am eliminat fiecare vârf din Q în această buclă while, în cele din urmă voi spune tuturor estimărilor de distanță la distanța reală și noi' va fi de aur. Zile fericite. În regulă. Deci vom termina dacă putem dovedi această afirmație. În regulă. Deci vom demonstra acest lucru prin inducție, evident. Inducția pe primele k noduri eliminate din Q. Deci, Q, vom scoate nodurile din acest Q într-o anumită ordine. Deci voi argumenta doar că această afirmație este adevărată pentru primul k. În mod clar, acest lucru este adevărat pentru k este egal cu 1. Caz de bază, k este egal cu 1. Ce este k egal cu 1? Asta înseamnă că primul vertex al cuvântului pe care l-am izbit are această proprietate, ceea ce este cu siguranță adevărat, pentru că am stabilit cea mai scurtă distanță la s să fie 0. Asta e bine. Acum avem pasul nostru inductiv. Să presupunem că este adevărat pentru k prim-- scuze, k mai mic decât k prim. Și să lăsăm v prim să fie k prim vârf. v prim. BINE. Și acum să ne uităm la cea mai scurtă cale de la s la v prim. Deci avem calea cea mai scurtă de la s la v prim. Exista. v prime este accesibil. Să presupunem că ne-am tăiat graficul pentru a fi doar lucrurile accesibile din s, astfel încât, da, există calea cea mai scurtă către v prim. Și acum să ne gândim la aceste vârfuri. Unele dintre ele au fost eliminate din Q, iar altele nu. s a fost cu siguranță eliminat din Q. Dar unele dintre aceste alte vârfuri ar putea să nu fie. Vreau să pot induce pe această cale, în special, vârful dinaintea mea, astfel încât să pot spune că atunci când l-am îndepărtat și relaxez muchia la v prim, atunci suntem cu toții aurii. Dar s-ar putea să nu fie cazul. Ar putea exista un vârf, vârful precedându-mă în grafic în această cale cea mai scurtă care nu a fost scoasă din Q. Trebuie să argumentez că a fost sau altceva. Deci, să luăm în considerare primul vârf din această cale de la s la v. Îl voi numi y, cred. Da. Un vârf y care nu este în Q. După I pop v prim, acesta este primul -- sau înainte de I pop v prim, y nu este în Q. Acum acestea ar putea fi același vârf dacă toate cele precedente de pe aceasta calea au fost în Q. Dar în special, ne vom uita la acest tip. Și spuneți x-ul predecesorului său în cale. Pai ce stiu? Știu că x este în coadă. Totul aici a fost scos din Q-- nu înăuntru. Ceea ce înseamnă că prin inducție, distanța pe calea cea mai scurtă a fost setată corect aici. Astfel încât distanța estimată la y nu poate fi mai mare decât cea mai scurtă cale către x plus w x, y. Dar aceasta este pe calea cea mai scurtă către y, deoarece subcăile celor mai scurte căi sau cele mai scurte căi. Deci, aceasta trebuie să fie egală cu d s, y, distanța până la y. Deci, de fapt, y este bine aici. Și deci dacă v prim ar fi y, am fi terminat. Acesta este același argument este relaxarea DAG. Dar trebuie să demonstrăm ceva despre v prim. Ei bine, pentru că avem greutăți nenegative, distanța până la v prim trebuie să fie cel puțin la fel de mare ca această distanță, deoarece este o cale secundară. Deci aceasta trebuie să fie mai mică sau egală cu distanța reală până la v prim. Din cauza ponderilor negative-- nenegative, deoarece ponderile sunt nenegative. Dar pentru că relaxarea este sigură, știm că distanța noastră estimată pentru v prim trebuie să fie cel puțin distanța pe calea cea mai scurtă. Asta pentru că este sigur. Aceasta este -- ponderile sunt mai mari sau egale cu 0. Ultimul pas aici este că, deoarece scoatem minimul din coada noastră de prioritate , lucrul cu cea mai mică distanță pe calea cea mai scurtă, aceasta trebuie să fie mai mică sau egală cu distanța pe calea cea mai scurtă estimată la y. Pentru că acesta este cel mai mic dintre toate astfel de vârfuri din Q-ul meu. Dar acestea au aceeași valoare. Deci totul dintre aici are aceeași valoare. În special, estimarea de aici este egală cu distanța mea adevărată pe calea cea mai scurtă, care este exact ceea ce încercăm să dovedim. OK, de aceea Dijkstra are dreptate. Voi petrece ultimele cinci minute pe durata de funcționare a Dijkstra. Am configurat acest lucru astfel încât să facem totul în ceea ce privește aceste operațiuni Q. Deci avem aceste operații Q, avem trei dintre ele. O să spun că dacă am o operațiune de construire, să presupunem că durează B timp; pentru a conduce min, am să spun că este nevoie de M timp; și această cheie scăzută, am să spun că durează D. Deci, care este durata de funcționare a Dijkstra? Dacă mă uit la acel algoritm de acolo... ei bine, cred că hai să le schimbăm din nou. OK, deci ce face asta? Construim o dată. Apoi ștergem minimul din Q de câte ori? v ori. Îndepărtăm fiecare vârf din Q. Apoi, pentru fiecare margine posibilă, ar putea fi nevoie să ne relaxăm și să reducem cheia din coada noastră o dată pentru fiecare margine de ieșire. Deci timpul de rulare este B plus V ori M plus E ori D. OK. Deci, cum am putea implementa această coadă de prioritate? Ei bine, dacă folosim cea mai stupidă coadă de prioritate din lume, iată o listă cu diferite implementări pe care le-am putea avea pentru cozile noastre prioritare. Și când spun coadă prioritară, mă refer la această coadă prioritară. Implementăm deja coada de priorități modificabile legând-o cu un dicționar care este eficient. Dacă folosesc doar o matrice, pot găsi minul în timp liniar, sigur. Și nu trebuie să actualizez acea matrice în niciun fel. Adică, pot să păstrez distanțele în matricea mea de acces direct. Nu trebuie să stochez o structură de date separată. Doar stochez distanțele în matricea mea de acces direct D și astfel îl pot găsi în timp constant și pot actualiza valorile stocate acolo. Și apoi, ori de câte ori vreau minim, pot doar să parcurg totul. Deci asta îmi oferă o tastă de scădere foarte rapidă, dar ștergere lentă min. Dar dacă ne uităm la timpul de rulare limitat aici, obținem ceva, dacă înlocuim n cu v, obținem un algoritm de timp pătratic în numărul de vârfuri, care pentru un grafic dens, acesta este în timp liniar. Asta e de fapt destul de bine. Dens, ceea ce înseamnă că am cel puțin un număr pătratic de vârfuri. Deci, asta este de fapt foarte bun și este cea mai stupidă structură de date posibilă pe care am putea-o folosi pentru această coadă de prioritate. Acum ne putem descurca puțin mai bine, de fapt, pentru nu dens-- Adică, pentru grafice rare unde numărul de muchii este de cel mult v, atunci acest lucru este destul de rău, este pătratic. Vrem să facem ceva mai bine. Acum, dacă suntem rari, un heap binar poate șterge min în timp logaritmic, dar poate, de fapt, dacă știu unde sunt în heap și scad cheia și sunt într-un min heap, pot doar să schimb cu părintele meu în sus în arbore în timp de log n și reechilibrează-- refix proprietatea heap binar. Și așa pot face asta în timp logaritmic. Și dacă fac asta și o pun în această formulă, de fapt obțin n-- sau V plus V ori log V plus E ori log V. Și așadar asta îmi va da E log V dacă presupun că eu' Mai întâi scot toate lucrurile care nu sunt conectate la mine, apoi E asimptotic limitele superioare V și obțin acest timp de rulare E log V , care este destul de bun. Acesta este doar un factor de logare suplimentar pe liniar. Acum există o și mai bună... ei bine , mai bine este greu de spus. Într-adevăr, există o structură de date diferită care atinge ambele limite pentru graficele rare și dense și tot ce se află între ele. Ne oferă o limită de timp de rulare E plus V log V. Această structură de date se numește heap Fibonacci. Nu vom vorbi despre asta în 6.006. Ei vorbesc despre asta-- și poți să te uiți la capitolul 19 din CLRS sau poți să te uiți la-- Cred că vorbesc despre asta în 6.854 dacă ești interesat să afli despre grămezi Fibonacci. Dar acestea nu sunt aproape niciodată... Adică, au limite teoretice bune. Deci ceea ce vrei să spui este că, ori de câte ori vă oferim o problemă de teorie în care ați dori să utilizați Dijkstra, doriți să utilizați acest timp de rulare teoretic legat pentru problema dvs. E plus V log V. Dar dacă se întâmplă să știți că graficul dvs. este rar sau dens, doar folosirea unei matrice sau a unui heap vă va oferi un timp de rulare la fel de bun. Foarte aproape de liniar. Și așa, în practică, majoritatea oamenilor, atunci când implementează un algoritm de căutare în graf , știu dacă graficul lor este rar sau dens, și astfel nu se deranjează niciodată să implementeze o grămadă Fibonacci, ceea ce este puțin complicat. Deci, de obicei, fie într- unul dintre aceste primele două cazuri în care V pătrat este liniar atunci când graficul este dens, fie suntem foarte aproape de liniar, E ori log V, care este V log V dacă graficul este rar. Deci, acesta este timpul de funcționare al Dijkstra. Până acum, am obținut toate aceste limite frumoase. Unele cazuri speciale în care suntem... Adică, cazuri speciale în care suntem liniari. Dijkstra unde suntem aproape de liniar. Și Bellman-Ford, dacă ne aruncăm mâinile în aer, ar putea fi cicluri negative în graficul nostru, trebuie să petrecem timpul de rulare pătratic legat. Acum există algoritmi mai rapizi , dar acesta este cel mai rapid pe care îl vom învăța în această clasă. Acum și în următoarea prelegere vom vorbi despre toate cele mai scurte căi de pereche și o vom relua data viitoare.