[SCRÂȘIT] [FOSȘIT] [DĂ CLIC] JASON KU: Bună, tuturor. Bun venit la a 11-a prelegere din 6.006, prima noastră prelegere despre cele mai scurte căi ponderate. Până acum, am vorbit doar despre grafice care-- unde măsuram distanța în termeni de număr de muchii dintr-o cale. Astăzi, vom generaliza această noțiune. Dar vreau doar să trec peste ceea ce am vorbit în ultimele două prelegeri. În ultimele două prelegeri, am vorbit despre doi algoritmi, căutarea pe lățimea întâi și căutarea în adâncime pentru a rezolva o serie de probleme. Iată câteva dintre problemele pe care le-am rezolvat. Cele mai scurte căi dintr-o singură sursă, unde distanțele sunt măsurate ca număr de muchii dintr-o cale. Și am folosit BFS pentru a rezolva această problemă, pornind de la o singură sursă, de obicei un vârf pe care îl numim. Și rezolvăm asta în timp liniar. Și rezolvăm asta în ordinea v plus e. Așa am numit timp liniar pentru un grafic. Pentru cazul special al accesibilității cu o singură sursă, aici a trebuit să returnăm cea mai scurtă distanță de cale pentru fiecare vârf. Și erau, cel mult, E lucruri accesibile dintr-un vârf. Deci aceasta este limita pe care o avem. Dar în cazul special pentru accesibilitatea cu o singură sursă, atunci când rezultatul nostru trebuie să enumere doar vârfurile care sunt accesibile de la mine, numărul de lucruri accesibile într- un arbore de acoperire a componentei conectate a sursei mele poate fi aproape de ordinul E. Și astfel, pentru toate nodurile singleton mici din graficul meu, nu-mi pasă cu adevărat. Așa că pot obține asta în ordinea E, dar asta este un fel de puțină optimizare. Următorul lucru pe care l-am făcut a fost că am vorbit despre componentele conectate. Și nu ne-am redus doar la utilizarea unui algoritm de căutare, cum ar fi un algoritm de accesibilitate cu o singură sursă, cum ar fi BFS sau DFS. Am pus o buclă pentru a explora întregul grafic, spunând practic, dacă am explorat o componentă conectată, atunci pot să mă uit la orice alt vârf pe care nu l-am văzut și să-l explorez pe următorul. Și așa că, de fapt, cu puțină analiză, am primit și timp liniar, pentru că cel mult traversez orice componentă a graficului meu o dată. Cam asta e ideea. Și putem folosi asta folosind BFS sau DFS într-adevăr, pentru că încercăm doar să obținem un lucru care caută o întreagă componentă conectată. Și apoi acest tip topologic am făcut-o la sfârșitul ultimei prelegeri. Am folosit DFS complet pentru a da o ordonare a nodurilor într-un DAG-- poate voi specifica clar că aceasta este doar pentru un DAG-- unde avem o ordonare a nodurilor, astfel încât toate muchiile merg înainte în acea ordine, pt. exemplu. Și asta am făcut și în timp liniar. În regulă, în această prelegere și, de fapt, în următoarele patru prelegeri, ceea ce vom face este în loc să măsurăm distanța în termeni de număr de muchii dintr-o cale-- deci anterior, distanța a egalat numărul de muchii-- Vom generaliza această noțiune. Deci, în loc să numărăm o margine, vom număra un număr întreg asociat cu acea margine. Se va numi o greutate. Deci, iată un exemplu de grafic ponderat G. Și am etichetat, cu roșu, ponderi pentru fiecare dintre aceste muchii. Acesta este un grafic direcționat pe opt vârfuri. Și am un număr întreg asociat cu fiecare margine. Veți observa, unele dintre ele sunt pozitive, altele sunt negative. Este în regulă să fie și zero. Aici este orice greutate de margine întreagă. Deci, în general, vom fi -- împreună cu graficul nostru G, ni se va da o funcție de greutate care mapează marginile lui G la, vom spune, oricum, numere întregi, în această clasă . În alte contexte, în matematică, s- ar putea ca acestea să fie numere reale. Dar în această clasă, ne vom ocupa de numere întregi. Deci, fiecare margine, dacă aveți o margine, vom spune că aceasta este greutatea marginii - greutatea acestei margini e, de la e. Uneori, dacă această muchie e este u, v, am putea spune uneori greutatea de la u la v, deoarece avem un grafic simplu care nu este ambiguu. Bine, deci, dar aici se vorbește doar despre notația noastră. Deci, în general, de exemplu, care este greutatea de la vârful b la f în acest grafic? Poate cineva sa-mi spuna? PUBLIC: Minus 4. JASON KU: Minus 4, nu? Este chiar aici. Și voi fi consecvent cu colorarea mea, pentru că am cretă colorată astăzi. Minus 4. Fericire. În regulă, de ce ne pasă să adăugăm greutăți la graficul nostru? Ei bine, acest lucru apare foarte mult în multe aplicații. De exemplu, distanțe într-o rețea de drumuri. dacă am un drum de aici, deci de la Mass Ave, în fața MIT, până la Central Square, am putea să ne gândim la asta ca pe un singur drum. Poate că fiecare drum este o legătură între două intersecții din rețeaua mea de drumuri. Dar un avantaj, durează mai mult pentru a merge de la, să zicem, Vassar Street la Amherst. Acest lucru durează mai puțin decât pentru a merge de la Memorial Drive peste râu la Beacon Street. Deci am putea dori să asociem o distanță mai mare sau o greutate asociată cu acea margine. Latența într-o rețea, de exemplu. Poate puterea relațiilor într-o rețea de socializare. Și ți-ai putea imagina că este posibil să fii „prieteni” cu cineva, să nu-ți placă și deci poate că ai o greutate negativă asociată cu un avantaj într- o rețea de socializare. Nu sunt sigur. Poate nu. Dar există o mulțime de aplicații în care s-ar putea să doriți greutăți pe margini. Așadar, vine la următoarea întrebare: cum reprezint... cum îi dau utilizatorului sau algoritmului aceste ponderi în graficul meu? Am avut o reprezentare pentru un grafic. Modul nostru obișnuit de a reprezenta un grafic a fost stocarea unei structuri de date stabilite pe nodurile mapate la adiacențele fiecărui vârf, pe care am stocat-o în ceea ce am numit o listă de adiacență, care într-adevăr ar putea fi orice structură de date. De obicei, este doar o serie de adiacente. Dar ați putea avea, de asemenea, să fie o structură de date setată, în care puteți interoga în timp constant ce-- dacă există o anumită adiacență în acel grafic. Deci, există două moduri comune de a stoca aceste greutăți. Una este doar că, cu fiecare adiacență, îi voi stoca greutatea. Poate doar într-un tuplu. Cu fiecare adiacență, stocați și greutatea marginii căreia îi corespunde , în orice fel. Un al doilea mod, în loc să încercăm să ne modificăm structura graficului pe care ți-am dat-o înainte, să avem doar un dicționar al tuturor marginilor care se apropie de greutățile lor. Și știm deja cum să facem asta. Doar orice set de structură de date - orice set separat de structură de date care mapează marginile la ponderile lor, cred. Notare proastă, dar ați înțeles ideea. Și nu contează cu adevărat cum facem asta. Presupunerea pe care ne vom baza aici este că, având în vedere o muchie, având în vedere această pereche de vârfuri, pot întreba care este greutatea acelei muchii în timp constant. Și așa că, dacă o să fac asta, îl pot stoca, poate, cu un tabel hash de tabele hash -- un tabel hash care mapează setul de vârfuri la adiacențele lor, iar apoi fiecare listă de adiacență își stochează adiacentele într-un tabel hash. . Și astfel, în timp constant, pot verifica ce greutate este acolo. Sau aici, sunt doar... Aș putea chiar să am un singur tabel hash care să mapeze perechea, marginea, tuplul, dimensiunea constantă, la greutatea sa. Deci oricum e bine. Vom presupune doar că putem interoga o margine în timp constant - greutatea unei margini în timp constant. OK, deci acesta este exemplul de grafic. E puțin aglomerat aici. Probabil că o voi șterge într-o secundă. Dar vom trece la ceea ce implică acordarea acestor ponderi laturi pentru aceste probleme pe care le-am definit în termeni de grafice neponderate. În special, ne vom concentra pe cele mai scurte căi dintr-o singură sursă , din nou, cel puțin pentru următoarele trei prelegeri. Vom generaliza asta chiar și în următoarea prelegere-- adică în a patra-- în trei prelegeri de acum înainte. Dar ceea ce am avut aici a fost că distanța dinainte într-un grafic neponderat era numărul de muchii din cale. Aici, vom generaliza această noțiune în mod evident la căi ponderate. Și greutatea unei cărări, o voi numi pi. Deci o pondere a căii pi va fi doar suma greutăților din marginile căii. Așa că la marginea căii, o să le însumez greutățile. Deci asta este tot ceea ce înseamnă greutatea unei căi. Doar că o să însumez toate greutățile dintr-o cale. Deci, dacă m-aș uita la... poate că există o cale anume aici. Calea de la a la b la f la g va fi minus 5, minus 4, 2. Va fi minus 9 plus 2 este minus 7. Deci, doar ca exemplu. Atunci care este calea cea mai scurtă? Ei bine, în mod evident, printre toate căile dintre două vârfuri, va fi una cu greutatea minimă. Da, întrebare. PUBLIC: Pot folosi aceeași margine de mai multe ori? JASON KU: Pot folosi aceeași margine de mai multe ori? Chiar acum, întrebați despre distincția pe care o avem în clasa noastră între căi și căi simple. Deci aici, unei cărări ponderate nu prea îi pasă dacă vizităm o margine de mai multe ori. Deci, dacă o muchie apare de mai multe ori în pi, trebuie să socotim aceasta de mai multe ori în greutatea muchiei - în greutatea căii. OK, grozavă întrebare. Dar ceea ce vom vedea mai târziu este că cele mai scurte căi nu pot repeta o margine de mai multe ori în anumite contexte. Așa că vom ajunge la problema de acolo puțin mai târziu în această prelegere. Și vom rezolva asta în prelegerea de mâine. Dar dacă ai... suntem puțin înaintea noastră. Dar când avem ponderi negative într-un grafic, este posibil ca lucrurile să meargă prost. Vom ajunge acolo în vreo cinci rânduri. Bine, minunat. Deci, cea mai scurtă cale-- și în acest caz, voi clarifica că aceasta este cea mai scurtă cale ponderată-- este un minim-- min-i-mum-- sigur-- este o cale minimă de greutate de la s la t . Nimic prea interesant aici, dar există de fapt niște subtilități cu care trebuie să ne confruntăm aici. Vom apela - la fel cum am făcut cu căutarea pe lățimea întâi când am vorbit despre cele mai scurte căi, vom defini o expresie pentru distanța sau greutatea căii celei mai scurte dintre două vârfuri. Și voi reprezenta asta printr-o deltă. O delta de la un vârf s la t va fi-- hai-- Voi face lucrul greșit mai întâi-- minimul peste greutatea tuturor căilor pentru toate căile pi de la s la t. OK, deci sunt câteva lucruri care merg prost aici. Primul lucru care merge prost este același lucru care a mers prost cu căutarea pe lățimea întâi. Își amintește cineva ce ar putea merge prost cu căutarea pe lățime a acestei definiții deltei? PUBLIC: Poate că nu există cale. JASON KU: Poate că nu există nicio cale, corect. Deci, cu excepția cazului în care nu există cale. Doar prin convenție, setăm delta s, t la infinitul egal. Dar există o problemă suplimentară cu cele mai scurte căi ponderate și este puțin subtilă. Este posibil ca o cale finită cea mai scurtă - cea mai scurtă lungime finită să nu existe. Și ce vreau să spun cu asta? Înseamnă că aș putea continua să trec prin margini în graficul meu și să obțin continuu o cale mai scurtă. Deci, dacă cea mai scurtă - greutatea minimă a unei căi de la s la t trece de fapt printr- un număr infinit de muchii, atunci aceasta nu este chiar bine definită. Așa că voi schimba acest minim aici în... în matematică, pentru a fi mai precis, am numi-o infimum. Deci, dacă în cazul în care greutatea unei căi cele mai scurte se poate apropia în mod arbitrar de mică, atunci vom numi acest lucru minus infinit. Deci când se întâmplă asta? Când se întâmplă asta? Când am putea avea calea noastră cea mai scurtă să treacă prin multe și o mulțime de vârfuri? Ei bine, haideți să aruncăm o privire la acest exemplu aici. Poate cineva să-mi spună care este calea cea mai scurtă de la a la orice vârf din acest grafic? PUBLIC: b, f, g, c. JASON KU: Ah, bine. Ei bine, am putea să ne uităm la această cale pe care trebuie să b. Să aruncăm o privire la b. Am o cale care merge de la a la b care este minus 5. OK, asta e destul de bine. E destul de mic. Și se pare că dacă ocolesc acest grafic printr-un alt mod, ar putea fi mai mare. Deci merg 7 plus 3 plus 8-- adică 15-- minus 1-- adică 14. Este mult mai mare decât minus 5, așa că se pare că minus 5 ar trebui să fie bun, nu? Are cineva o problemă cu această cale sau o problemă cu aceasta fiind cea mai scurtă cale? Și ceea ce tocmai mi-a informat colegul tău a fost că se întâmplă ceva interesant în acest grafic în special. Avem un ciclu de la b la f la g la c care are greutate totală negativă înapoi la b. Acesta are minus 4 plus 2 plus 1 minus 1. Deci acel ciclu total are o greutate a ciclului de minus 2, acest ciclu de greutate negativă. Deci, dacă vreau să ajung la b, aș putea merge acolo prin acest minus 5 greutate. Dar de fiecare dată când mă întorc în jurul acestui ciclu, suportam minus 2 față de greutatea traseului meu. Așa că continui să ocolesc acest ciclu iar și iar și iar și iar și iar și nu am nicio cale de greutate minimă de lungime finită. Și în astfel de cazuri, spunem doar că delta este minus infinitul. Deci problema aici este că am putea avea cicluri negative de pondere-- merită o majusculă-- Cicluri de ponderi negative. E o problemă. În special, dacă există o cale de la s la un vârf v care trece printr-un vârf într-un ciclu de pondere negativă, atunci pot lua acea cale către acel vârf, pot face o cerc în jurul ciclului de pondere negativă și apoi merg la v și I pot face acel ciclu de câte ori vreau. Apoi această delta s,v o vom seta la minus infinit. Și în astfel de cazuri, în algoritmul nostru cu cele mai scurte căi, nu ne pasă cu adevărat care este calea cea mai scurtă. Nici măcar nu ne vom ocupa de pointerii părinte aici, deoarece nu există o cale mai scurtă cu lungime finită. Așa că o să- mi ridic mâinile în aer și să-ți spun, știi ce, nu-ți pot întoarce o cale cea mai scurtă, dar s-ar putea să vreau să-ți revin la un ciclu negativ al greutății. Dacă mi-ai spus că chestia asta are o greutate slabă, poate vreau să- mi spui care este calea care trece printr-un ciclu de greutate negativ pentru a reveni la s. Deci despre asta vom vorbi următoarea prelegere. Această prelegere, nu vom vorbi despre asta. Totuși, vom vorbi despre cele mai scurte căi ponderate . Despre asta se referă cu adevărat restul acestei unități despre grafice este căile cele mai scurte ponderate. OK, deci în căile cele mai scurte ponderate, știm deja un algoritm pentru a rezolva un subset de părți cele mai scurte ponderate, și anume BFS, nu? Acum, ești ca și cum stai, Jason, BFS nu rezolvă cele mai scurte căi ponderate. Nici măcar nu știam despre graficele ponderate atunci. Cum rezolvă asta cele mai scurte căi ponderate? Ei bine, există câteva cazuri în care am putea să ne reducem la rezolvarea celor mai scurte căi folosind BFS. Se poate gândi cineva la un astfel de scenariu? Deci, să spunem, adică, cam ceea ce am făcut înainte a fost să numărăm numărul de muchii. Deci, dacă am dat o pondere de 1 fiecărei muchii din graficul meu, atunci doar acel grafic, acel grafic ponderat, corespunde unui grafic neponderat folosind cealaltă metrică de distanță. Deci, în acest caz, BFS ne rezolvă problema. Și de fapt, putem generaliza mai departe. Ce se întâmplă dacă toate ponderile noastre ar fi pozitive, dar aceeași valoare? Dacă ar fi totul pozitiv și aceeași valoare, atunci am putea doar împărți cu acea valoare. Acum avem un grafic neponderat pe care îl putem rula BFS și apoi înmulțim cele mai scurte distanțe de cale cu acea valoare mai târziu. Și, de fapt, mai există o generalizare suplimentară pe care o putem face, care este puțin o problemă complicată de transformare a graficului . Dar putem obține și acest algoritm de timp liniar pentru cele mai scurte căi ponderate cu o singură sursă în contexte în care ponderile nu sunt atât de mari. Deci, dacă am greutăți de margine pozitivă-- dacă am o greutate de margine pozitivă, să zicem -- folosind culoarea mea de greutate aici -- asta este, de exemplu, greutatea de 4, este un fel de problematică, pentru că nu știu cum să simulez că folosind un grafic neponderat. Sau eu? Are cineva o idee despre cum aș putea simula o margine de greutate 4 cu un grafic neponderat? Da. PUBLIC: Aveți patru margini ale greutății 1. JASON KU: Da, pot doar să pun patru margini ale greutății 1 în paralel aici-- Îmi pare rău, în serie, opusul paralelului. Pot doar converti acest lucru aici în 1, 2, 3, 4 muchii. Și dacă fac asta pentru fiecare muchie din graficul meu și avem ponderi de margine pozitivă, atunci acea transformare poate rezista. Acum, asta nu este neapărat o transformare bună de făcut. De ce? PUBLIC: Greutatea ar putea fi foarte mare. JASON KU: Da, ponderile ar putea fi foarte mari în comparație cu numărul de vârfuri și muchii din graficul meu. Cu toate acestea, dacă suma tuturor greutăților din graficul meu este asimptotic mai mică decât v plus e, putem obține din nou un algoritm de timp liniar prin reducerea la BFS. OK, așa că e grozav. Dar, în general, asta ne oferă un algoritm de timp liniar în aceste cazuri foarte speciale. Și, în general, este o problemă deschisă. Nu știm dacă putem rezolva problema căilor cele mai scurte cu o singură sursă în context ponderat pentru grafice generale în timp liniar. Nu știm cum să o facem. Dar ceea ce știm sunt niște algoritmi care se descurcă destul de bine. Și asta folosim tot timpul. Dar încă un caz special pe care îl vom analiza astăzi este când avem această structură foarte frumoasă în care avem un DAG, un Grafic Aciclic Dirijat , așa cum vorbeam în ultima prelegere. Pentru orice set de greutăți de margine -- țineți minte, cu BFS, trebuia să ne limităm greutățile de margine pentru a fi pozitive și poate limita pentru a obține acest timp bun de rulare? Pentru orice set de greutăți de margine, dacă structura noastră grafică este DAG -- într-adevăr nu are nimic de-a face cu ponderile -- dacă structura graficului este un DAG, atunci putem rezolva de fapt această problemă cu cele mai scurte căi cu o singură sursă în timp liniar, ceea ce este destul de grozav. Acum, pentru grafice generale, vă vom arăta în următoarea prelegere cum să, pentru orice grafic -- chiar și cu cicluri, chiar și cu cicluri cu greutate negativă -- vă vom arăta cum să rezolvați această sursă unică. Problema cu cele mai scurte căi într-o limită de timp de rulare pătratică. Acum, acesta nu este cel mai cunoscut, dar este un algoritm cu adevărat practic și oamenii îl folosesc tot timpul. Și vom arăta Bellman-Ford în contextul algoritmului DAG pe care îl vom rezolva astăzi. Deci, acesta este cazul foarte general în ceea ce privește restricțiile pe graficul nostru. Dar, în realitate, cele mai multe probleme care apar în aplicații apar cu grafice care au ponderi de margine pozitivă. Vă puteți gândi la o rețea de drumuri. Oricum ai... sau nu sunt negative. Călătorești de-a lungul și nu este niciodată util să te întorci de unde ai venit, pentru că vrei să faci progrese până unde mergi. Deci, în contextul în care nu aveți greutăți negative, nu aveți această problemă în care aveți cicluri negative de greutate . De fapt, putem face mult mai bine exploatând această proprietate. Și obținem o legătură care este un pic-- care arată puțin mai mult ca n log n. Este destul de aproape de liniar. Pierzi un factor de logare a numărului de vârfuri. Dar e destul de bine. Aceasta se numește Dijkstra și vom ajunge la asta în două prelegeri. OK, deci aceasta este foaia de parcurs a ceea ce vom face pentru cel puțin următoarele trei prelegeri. Dar înainte de a vă arăta cum să rezolvați cele mai scurte căi dintr-o singură sursă într-un DAG folosind acest algoritm pe care îl numesc relaxare DAG aici, mă voi întoarce la un lucru despre care am vorbit în căutarea pe lățime. , unde în căutarea pe lățime, când am rezolvat cele mai scurte căi dintr-o singură sursă , scoatem două lucruri. Emitem cele mai scurte căi dintr-o singură sursă, aceste delte, pentru cealaltă definiție a distanței, greutățile -- Adică, nu greutățile, distanțele, cele mai scurte distanțe. Dar am returnat și indicații pentru părinți. Returnăm indicatorii părinte înapoi de-a lungul căilor către sursă pe cele mai scurte căi. Numim asta arborele celor mai scurte căi. Așa că voi revedea acest subiect despre arborele cu cele mai scurte căi -- arbori cu cele mai scurte căi -- arbori cu cele mai scurte căi. Și, în special, va fi cam enervant să vorbim despre ambele cantități -- distanțe și indicatori părinte -- pe măsură ce trecem prin toți acești trei algoritmi. Practic, va fi evidența contabilă pentru a-- distanțele sunt de fapt suficiente pentru ca noi să reconstruim indicatorii părinte dacă avem nevoie de ele mai târziu. Deci, ceea ce vă voi arăta -- vă demonstrez acum este că, dacă vă dau cele mai scurte distanțe de cale pentru submulțimea graficului accesibil de la s care nu trece prin cicluri de greutate negative, dacă sunt oferindu-vă acele distanțe, pot reconstrui indicatorii părinte de-a lungul celor mai scurte căi în timp liniar pentru orice grafic pe care vi l-aș putea oferi dacă vă dau acele distanțe cele mai scurte. OK, așa că asta voi încerca să vă arăt acum. Deci iată algoritmul. Pentru ponderat... aici este o avertizare pe care o voi nota. Pentru cele mai scurte căi ponderate, au nevoie doar de indicatori părinte pentru v cu distanța cea mai scurtă finită a căii -- doar cea mai scurtă distanță finită a căii. Nu ne pasă de cele infinite sau de cele minus infinite , doar de cele finite. OK, deci iată algoritmul. Pot să inițializez toate Pv-ul la egal... Îmi pare rău , oh, am fost înaintea mea. Scriu DAG. Inițiază structura de date a indicatorului părinte să fie goală. La început, nu voi sorta niciun indicator pentru părinți. Dar la început, voi seta indicatorul părinte al sursei să fie niciunul. Așa că asta am făcut și noi în căutarea pe lățime. Acum, ceea ce ți-am dat este... Încerc să arăt că, având în vedere toate cele mai scurte distanțe de drum, pot construi corect acești indicatori părinte. Deci, ceea ce voi face este, pentru fiecare vârf u din graficul meu, unde delta mea s din u este finită, ce voi face? Am de gând să spun, ei bine, să aruncăm o privire la toți vecinii mei plecați. Acesta este un fel de ceea ce facem în fiecare algoritm grafic. Pentru fiecare v din adiacență, adiacențele de ieșire ale lui u, dacă nu există niciun pointer părinte alocat acestui v, există potențialul ca i-- u-- [ CHUCKLES] I, you-- acest u, acest vârf u, este părintele lui v. Este posibil. Este o margine de intrare la v. Când va fi o margine de intrare la v? Dacă v nu este în P-- nu i-am atribuit un pointer părinte-- și-- deci asta înseamnă că ar putea fi părintele meu. Când este părintele meu pe calea cea mai scurtă? Sigur. PUBLIC: Însumează distanța de-a lungul marginii la distanța celuilalt. JASON KU: Da, deci avem un avantaj de la u la v. Are ceva greutate. Dacă știu deja cea mai scurtă distanță de cale până la u și știu cea mai scurtă distanță de cale până la v, dacă cea mai scurtă distanță de cale de la s la u - să desenăm o imagine aici. Avem s, avem o cale aici către u și știm că avem o margine de la u la v. Dacă această distanță cea mai scurtă a căii plus această greutate a muchiei este egală cu cea mai scurtă distanță a căii de la s la v , atunci e mai bine-- Adică, pot exista mai multe căi cele mai scurte, dar aceasta este cu siguranță cea mai scurtă cale, așa că putem aloca un pointer părinte înapoi lui u. Deci, să scriem acea condiție. Dacă distanța cea mai scurtă de la s la v este egală cu cea mai scurtă distanță de la s la u și apoi traversarea muchiei de la u la v, atunci există calea cea mai scurtă care folosește muchia u, v, în special aceasta. Deci setați părintele u-- din v la u. OK, deci acesta este algoritmul. Nu am de gând să- ți demonstrez că acest lucru este corect. Dar are un fel de sens intuitiv, nu? Dacă am aceste distanțe cele mai scurte de cale, puteți demonstra prin inducție că acest indicator părinte nu numai că indică locul potrivit de-a lungul celei mai scurte căi aici, dar o face și în timp liniar, deoarece fac bucla peste toate vârfurile și buclă peste adiacențele sale de ieșire o dată. În esență, aceeași analiză ca și pentru BFS și DFS. Și apoi, din moment ce putem face acest lucru, deoarece putem calcula indicatorii părinte de la aceste distanțe, vom ignora calcularea acestor indicatori părinte de acum înainte. Ne vom concentra doar pe calcularea distanțelor, pentru că oricum va trebui să luăm timp liniar cel puțin. Și toate celelalte lucruri necesită mai mult timp. Deci putem calcula distanțele în mai mult timp și apoi să calculăm părinții după. OK, deci asta vom face. Așa că acum, cu toată această acumulare, să arătăm un algoritm. [CHUCKLES] Cum calculăm cele mai scurte căi dintr-o singură sursă într-un DAG în timp liniar? Ei bine, un DAG-- Adică, acesta este de fapt un lucru super util și convenabil în algoritmi în general. DAG-urile sunt doar lucruri frumoase. Sunt într-un fel ordonate. Există această ordine de sortare topologică despre care vorbeam înainte. Acest lucru va juca un rol cheie. Există o structură foarte bună pentru DAG-urile care nu au cicluri, nu trebuie să se ocupe de această problemă negativă a ciclului de greutate. Puteți merge doar într-o singură direcție de-a lungul acestui grafic. Este o structură foarte frumoasă de exploatat. Și așa o vom exploata. Și iată ideea. Relaxare DAG, ceea ce va face este că va începe cu niște estimări ale acestor distanțe. Așa că mențineți estimările de distanță. Și acum voi încerca să fiu atent la modul în care îmi desenez D-urile. Acesta este un d, acesta este o deltă. Acestea sunt cele mai scurte căi. Aceasta este o estimare a distanței. Așa că asta voi folosi în restul acestui timp. Deci vom menține aceste estimări ale distanței d, care vor începe inițial la infinit. Nu știu ce sunt. Nu știu care sunt cele mai scurte căi, dar mai bine să fie mai puțin decât infinite sau nu-mi pasă. Deci, acesta este cel mai rău scenariu. Nu poate fi mai rău decât asta... pentru fiecare vârf. Și vom menține proprietatea care estimează limita superioară-- probabil că ar trebui să fie două cuvinte-- limita superioară delta s, v-- vom susține că ei delimitează acest lucru și, treptat, scad până când" sunt egali. Deci aceasta este ideea. Pornim de la o supraestimare, o limită superioară a estimării distanței. Și apoi vom scădea în mod repetat această valoare pe măsură ce obținem mai multe informații despre grafic, menținând că întotdeauna limităm distanța superioară. Și vom continua să o facem, să o facem, să o facem până când, așa cum vom încerca să vă dovedim, aceste estimări ajung, de fapt, ajung în jos, până la cele mai scurte distanțe ale noastre. Atunci când coborâm aceste lucruri? Când coborâm aceste lucruri? Vom reduce aceste estimări ale distanței ori de câte ori estimările distanței încalcă ceea ce vom numi inegalitatea triunghiului. OK, care este inegalitatea triunghiului? Inegalitatea triunghiulară este de fapt o noțiune destul de intuitivă. Practic spune că dacă am trei puncte-- prin urmare, triunghi-- poate mai mare ca să pot scrie o scrisoare în ele. Practic spune că, dacă am un vârf u, un vârf v, un vârf x, de exemplu, cea mai scurtă distanță de cale -- cea mai scurtă distanță de cale a delta a lui u, v -- aceasta este cea mai scurtă distanță de la u la v -- se poate nu fi mai mare decât cea mai scurtă cale de la u la v care trece și prin x. Dintre căile mele, acum restricționez căile pe care le am la cele care trec prin x. Cea mai scurtă distanță de cale de la u la v nu poate fi mai mare decât restricționarea căilor care trec prin x și luarea acelei distanțe cele mai scurte, obținerea celei mai scurte distanțe de drum de aici și adăugarea acesteia la cea mai scurtă distanță de cale aici -- delta u, x, delta x, v. Aceasta este doar o declarație a, mă limitez la un subset de căi. Nu pot să-mi reduc distanța minimă. Deci aceasta este afirmația inegalității triunghiului, că cea mai scurtă distanță a căii de la u la v nu poate fi mai mare decât cea mai scurtă distanță a căii de la u la x plus cea mai scurtă distanță a căii de la x la v pentru orice x din graficul meu care nu este u și v. Deci aceasta este inegalitatea triunghiului. O noțiune destul de intuitivă, nu? De ce este util acest lucru? Bine, bine, dacă găsesc-- dacă găsesc o margine în graficul meu, dacă există o margine u, v, în graficul meu astfel încât această condiție este încălcată pentru estimările pe care le am-- evident că nu poate fi încălcată pe cele mai scurte distanțe ale mele, dar dacă o încalcă la estimări-- u, v, este mai mare decât u, x-- îmi pare rău, u-- cum voi face asta? Vreau ca acesta să fie s. Eu calculez cele mai scurte distanțe de la s și cele mai scurte distanțe de la s la un vârf de intrare u plus greutatea marginii de la u la v. Bine, deci ce face asta? Am niște margini u, v în graficul meu. Practic, ceea ce am spus este că am o estimare a distanței până la u, dar trecând prin-- fac o cale către v trecând prin u, iar apoi marginea de la u la v este mai bună decât estimarea mea actuală, cea mai scurtă cale a mea estimare la v. Asta e rău, nu? Asta încalcă inegalitatea triunghiului. Acestea nu pot fi greutățile potrivite. Acestea nu pot fi distanțele potrivite. Deci, cum vom face asta este mai mic - asta este ceea ce am spus, mai mici aceste estimări ale distanței. Îl voi coborî pe tipul ăsta pentru a egala chestia asta. Într-un fel, această constrângere a fost încălcată. Dar acum relaxăm această constrângere, astfel încât aceasta să nu mai fie încălcată. Așa că relaxează-te este un cuvânt puțin ciudat aici. Îl folosim din motive istorice. Dar la asta ne referim când spunem relaxați-vă. Acest lucru este o constrângere încălcată. Are ceva presiune de rezolvat. Și, deci, ceea ce facem este că, pentru a o rezolva, îl setăm pe acest tip egal cu asta, astfel încât cel puțin să rezolve, la nivel local, acea constrângere. Acum, poate încălca inegalitatea triunghiului în alte locuri, acum că am făcut această schimbare. Dar cel puțin această constrângere este acum relaxată și satisfăcută. OK, așa că relaxează marginea scăzând d din s, v la acest lucru. La asta vom înțelege prin relaxarea unei margini. Iar relaxarea unui avantaj este ceea ce voi numi sigur. Este sigur de făcut. Ce vreau să spun prin relaxarea este sigură? Înseamnă că, pe măsură ce calculez cele mai scurte distanțe ale căii, voi menține această proprietate că fiecare dintre aceste estimări -- îmi pare rău, aceste estimări aici -- are proprietatea că fie este infinită, fie este greutatea unei căi. la v. Deci, acesta este lucrul -- relaxarea este sigură. OK, deci fiecare estimare a distanței, s, v, este greutatea unei căi de la s la v sau infinit. Și acesta este un lucru destul de ușor de demonstrat. Dacă aș avea invarianta că toate acestea erau greutăți ale celor mai scurte căi, să încercăm să relaxăm o margine. Și trebuie să arătăm că această proprietate este menținută. Relaxează-te pe marginea u, v, bine? Acum, dacă mă relaxez pe marginea u, v, ce fac? Am setat acest lucru-- sau, scuze, am setat acest lucru, cea mai scurtă distanță de cale a mea la v, să fie acest lucru plus acest lucru. Există o greutate a unei margini de la u la v. Acum, prin presupunerea mea că menținem că aceasta este greutatea unei căi din graficul meu, dacă acest lucru este mai mare, o setez la greutatea unei căi. pe graficul meu către u, plus o margine de la u la v, și așa se verifică. Deci, atribuiți d din s, v ponderii unei căi. Nu am de gând să notez toate argumentele pe care tocmai le-am avut aici. Dar, practic, deoarece această estimare a distanței a fost prin presupunere înainte de greutatea unei căi către v-- la u, atunci aceasta este, din nou, greutatea unei căi către v. OK, grozav. Deci acum suntem gata să trecem efectiv prin acest algoritm. Deci, relaxarea DAG, de acolo, inițializează toate estimările noastre de distanță la infinit, la fel cum am făcut în BFS. Apoi, setați estimarea distanței mele la 0. Acum, este posibil ca acesta să fie minus infinit sau negativ la un moment dat. Dar chiar acum, o setez la 0. Și oricum, 0 va limita superioară distanța la s. Deci, în special, la inițializare, orice nu este accesibil de la s este setat corect. Și s în sine este setat ca o limită superioară la cea mai scurtă distanță de cale. Acum vom procesa fiecare vârf u într-o ordine de sortare topologică . Așa că nu uitați, contribuția noastră pentru relaxarea DAG este un DAG. Deci chestia asta are o ordine de sortare topologică. Vom procesa aceste vârfuri în această ordine. Vă puteți imagina că începem de la vârf și toate vârfurile mele sunt... toate marginile mele sunt îndreptate departe de mine. Și doar procesez fiecare vârf în jos pe această linie de sortare topologică. Și apoi pentru fiecare dintre aceste vârfuri, ce voi face? O să mă uit la toți vecinii care ies. Și dacă inegalitatea triunghiului este încălcată, voi relaxa acea margine. Algoritmul este la fel de simplu. Pentru fiecare vecin care pleacă de la v-- îmi pare rău, de u-- eu întotdeauna am amestecat u și v aici. Dacă estimarea căii mele celei mai scurte la v încalcă inegalitatea triunghiului pentru o muchie, pentru o muchie de intrare, atunci voi stabili - relaxează u, v, adică setez d, s,v, egal cu d, s,u, plus w, u,v. Deci acesta este algoritmul. Deci, dacă ar fi să arunc o privire la acest exemplu de grafic de aici, poate că un este vârful meu de început. Îl inițializez pentru a-- PUBLIC: DAG. JASON KU: Acesta nu este un DAG. Mulțumesc. Să-l facem un DAG. Vă pretind acum că acesta este un DAG. În special, o ordine de sortare topologică este atunci când există o cale prin toate vârfurile, atunci există o ordine de sortare topologică unică - a, b, e, f, g, h, d, c. Aceasta este o ordine topologică. Puteți verifica toate marginile. Deci, voi începe prin a seta... de fapt, să folosim e. Să folosim cele mai scurte căi de la e. De ce nu? Cele mai scurte căi de la e. Vârful a vine de fapt înaintea e în ordinea topologică. Deci nu are... Adică , cea mai scurtă distanță de cale, când inițializez, voi inițializa asta la 0. Voi inițializa asta la infinit, infinit, infinit, infinit, toate aceste lucruri la infinit. Acestea sunt estimările mele. Acestea nu sunt încă cele mai scurte căi - distanțe. Dar când ajung aici, în mod clar nu pot fi... distanța față de mine fiind infinit nu poate încălca niciodată inegalitatea triunghiului cu ceva infinit sau finit. Nu contează, nu? Deci nu-i fac nimic unui. Orice înainte de vârful meu sursă în ordinea topologică nu poate fi vizitat, deoarece este înainte în ordinea topologică. Cam asta e ideea. Nu există nicio cale de la vârful meu sursă la nimic înaintea lui în ordinea topologică. La fel și cu b. b este înaintea lui a în ordinea topologică. Acum, sunt la e, și este posibil să încălcăm inegalitatea triunghiulară, în special aici. Cred că cea mai scurtă distanță de cale până la f este infinită. Dar, de fapt, dacă trec la e prin această muchie cu o greutate 3, știu că aceasta încalcă inegalitatea triunghiului. Deci, de fapt, acest lucru este greșit și îl pot seta egal cu 3. Acum, aceasta ar putea să nu fie cea mai scurtă distanță de cale. Dar acum este o estimare mai bună , așa că am stabilit-o. Acum, merg mai departe. Am terminat cu tipul ăsta. Trec la următorul vârf în ordinea topologică. Și din nou, relaxez marginile din f. OK, deci aici, uitându-ne la 8, 3 plus 8 este mai bun decât infinit, așa că vom spune că este 11. Și 3 plus 2 este mai bun decât infinit, deci este 5. Acum, continui în ordinea topologică. g este următorul. 5 plus 1 este 6. OK, așa că am găsit o estimare mai bună aici. Deci acest 11 nu este la fel de bun. 6 este mai bun, așa că îl înlocuim. Aici, nu am mai vizitat. Este încă infinit. Deci 5 plus minus 2 este 3. Acesta este următorul în ordinea topologică. 3 plus 9 este mai mare decât 6, așa că nu este o cale mai scurtă. 3 plus 4 este cu siguranță mai mic decât infinit, așa că setați-l egal cu 7. Apoi, 7 plus 5 este, de asemenea, mai mare decât 6. Și, de fapt, puteți confirma că toate acestea sunt cele mai scurte distanțe de cale de la e. Deci acest algoritm pare să funcționeze. Chiar funcționează? Hai să aruncăm o privire. Pretenția dvs. este că, la sfârșitul relaxării, acest algoritm, am stabilit-- susține la sfârșit, toate estimările sunt egale cu cele mai scurte distanțe de cale. Ideea de bază aici este că dacă iau k-lea vârf în ordinea topologică, presupunând că aceste distanțe sunt toate egale pentru cele dinaintea mea în ordinea topologică, pot demonstra prin inducție. Putem lua în considerare o cale cea mai scurtă de la s la v, k-lea vârf, și să ne uităm la vârful care mă precede pe calea cea mai scurtă. Acest vârf ar fi bine să fie în fața mea în ordinea topologică sau nu suntem un DAG. Și am stabilit deja cea mai scurtă distanță de cale să fie egală cu lucrul corect prin inducție. Așa că atunci când am procesat u-- s to u to v-- când am procesat u în relaxare DAG aici, am procesat vârful și am analizat toate adiacențele sale de ieșire , am fi relaxat această margine pentru a nu fi mai mare decât cea mai scurtă distanță de cale. . Deci asta este corect. De asemenea, vă puteți gândi la asta ca algoritmul de relaxare DAG pentru fiecare vârf se uită la vecinii săi de intrare, presupunând că distanța lor cea mai scurtă a căii sunt deja calculate corect. Orice distanță de calea cea mai scurtă până la mine trebuie să fie compusă dintr-o distanță de cale cea mai scurtă până la unul dintre vecinii mei care vin printr-o margine până la mine, astfel încât să le pot verifica pe toate. Asta face relaxarea DAG. Și din nou, facem buclă peste fiecare vârf și ne uităm la adiacențele acestuia, lucrând constant. Acest lucru, din nou, necesită timp liniar. OK, deci sunt cele mai scurte căi și un DAG. Data viitoare, ne vom uita, pentru grafice generale, cum putem folosi cam aceeași tehnică într-un algoritm pe care îl numim Bellman-Ford. OK, asta e tot pentru azi.