[SCRÂTÂND] [FOȘIT] [DĂ CLIC] JASON KU: OK, să începem. Bun venit la a 12-a prelegere din 6.006. Aceasta este a doua noastră prelegere despre grafice ponderate și, în special, despre cele mai scurte căi ponderate, algoritmi. Ultima dată am vorbit despre grafice ponderate. Acesta este un fel de generalizare a ceea ce înțelegem prin distanță într-un grafic neponderat, în loc ca fiecare muchie să aibă o pondere de 1, în esență. Generalizăm că este orice număr întreg. Și ultima dată, am arătat cum să rezolvăm cele mai scurte căi de o singură sursă cele mai scurte într-un grafic care nu are cicluri, chiar dacă are 0 sau ponderi negative în timp liniar, folosind un algoritm numit relaxare DAG. Am arătat, de asemenea, în acea prelegere cum, în timp liniar, dacă ni se dau cele mai scurte greutăți ale drumului către toate lucrurile accesibile în finit - sau cu cea mai scurtă distanță de cale care este finită, putem construi un arbore cu cele mai scurte căi din acele greutăți în timp liniar. Deci, acesta este motivul pentru care nu vom vorbi cu adevărat despre indicațiile părinților pentru următoarele două prelegeri. Ne vom concentra doar asupra greutăților pe calea cea mai scurtă. Și așa că astăzi, vom vorbi despre algoritmul nostru cel mai general pe care îl vom arăta pentru rezolvarea celor mai scurte căi cu o singură sursă, în special în grafice care ar putea conține cicluri și ar putea avea ponderi negative. Așadar, pentru a recapitula aici mica noastră foaie de parcurs, cele mai scurte căi cu o singură sursă în timp liniar. Ultima dată am discutat despre un alt algoritm de timp liniar, relaxarea DAG. Și astăzi vom vorbi despre Bellman-Ford, care nu se limitează la grafice asimptotice. În special, ar putea exista cicluri negative de greutate în graficul nostru. Dacă are cicluri, dacă are ponderi negative, îngrijorarea este că am putea avea cicluri de ponderi negative, caz în care acolo-- dacă un ciclu de ponderi negative este accesibil de la sursa noastră, atunci vârfurile din acel ciclu și orice este accesibil din acel ciclu. ciclul va avea potențial un număr nelimitat de muchii pe care trebuie să le parcurgeți. Nu există o limită a numărului de margini pentru cea mai scurtă cale, pentru că aș putea continua să ocolesc acel ciclu de câte ori vreau și să obțin o cale mai scurtă. Și astfel atribuim acele distanțe să fie minus infinitul. Așa că asta vom face astăzi în Bellman-Ford. În special, ceea ce vom face este să calculăm cele mai scurte distanțe ale drumului nostru, cea mai scurtă cale așteaptă fiecare vârf din graficul nostru, setându-le pe cele care nu sunt accesibile la infinit și pe cele care sunt accesibile printr-un ciclu de greutate negativă la minus infinitul și toate celelalte pe care le vom seta la o greutate finită. Și un alt lucru pe care ne-am putea dori este, dacă există un ciclu de greutate negativ în grafic, să returnăm unul. Deci acestea sunt cele două tipuri de lucruri pe care încercăm să le rezolvăm în prelegerea de astăzi. Dar înainte de a face asta, să ne încălzim cu două exerciții scurte. Primul, exercițiul 1, având în vedere un grafic nedirecționat, având în vedere graficul nedirecționat G, returnează dacă G conține un ciclu de pondere negativă. Are cineva o idee despre cum putem rezolva asta în timp liniar, de fapt? De fapt, o putem face în ordinea E. Nu... da, da. Accesibil de la S. Cred că... să spunem doar un ciclu negativ al greutății. Nu în contextul celor mai scurte căi cu o singură sursă. PUBLIC: Detectați dacă există o margine negativă de greutate? JASON KU: Ah. Colegul tău a determinat un fapt interesant despre graficele nedirecționate. Dacă aveți o margine de greutate negativă într-un grafic nedirecționat, mă pot mișca înainte și înapoi de-a lungul acelei margini. Acesta este un ciclu de lungime 2-- sau cred că trei vârfuri înapoi de unde am venit. Există o greutate negativă, pentru că doar parcurg această greutate iar și iar și iar. Deci problema căilor cele mai scurte de la o singură sursă de găsire a ponderilor negative nu este deosebit de interesantă în cazul nedirecționat. Ceea ce pot face este doar pentru fiecare muchie negativă de greutate, margine nedirecționată din graficul meu, pot găsi doar lizibilitatea de la vârfuri - punctele finale ale acelei muchii și să le etichetez ca minus - practic dacă componenta conectată care conține S are un marginea ponderii negative, atunci totul din grafic este accesibil dintr-un ciclu de ponderi negative. Deci aceasta nu este o problemă atât de interesantă. Și așa ne vom limita discuția de astăzi la grafice direcționate. Deci aceasta este dacă și numai dacă există o margine negativă a greutății. OK, exercițiul 2, un fel de mică previzualizare pentru ceea ce urmează, de fapt nu vă vom arăta un algoritm direct care să îndeplinească acest timp de rulare Bellman-Ford , de V ori E. În schimb, ceea ce vă vom arăta este un algoritm care rezolvă cele mai scurte căi dintr-o singură sursă în-- Deci, dat un algoritm, Alg A, rezolvă cele mai scurte căi dintr-o singură sursă în ordinea V ori V plus E timp. OK, ce este asta? Acesta este V pătrat plus V ori E. Este aproape de ceea ce este acest V ori E. Asta vă vom arăta. Dar dacă aș avea un astfel de algoritm, poate cineva să- mi spună un algoritm cu cele mai scurte căi cu o singură sursă - cum putem folosi acest algoritm pentru a rezolva cele mai scurte căi dintr-o singură sursă în doar V ori E timp? Arată cum să rezolvi SSSP în ordinea de V ori E. Cred că putem pune și un punct acolo. Deci acest lucru este puțin complicat. Este oarecum legat de diferența pe care am avut-o între problema accesibilității și problema celei mai scurte căi cu o singură sursă pe care am văzut-o ultima prelegere. Când sunt acestea diferite din punct de vedere asimptotic în limita lor superioară, este atunci când V este asimptotic mai mare decât E. Dar componenta conexă care conține S poate avea cel mult E vârfuri, sau de ordinul E. De fapt, poate avea cel mult E plus 1 vârfuri, pentru că altfel nu ar fi nu fi conectat. Deci, ce putem face dacă am avea un astfel de algoritm, am putea mai întâi, atunci când dăm graficul nostru, să explorăm totul din grafic folosind BFS sau DFS, să găsim toate lucrurile accesibile din S și apoi să aruncăm orice altceva. . Acum am un grafic pentru care V nu este asimptotic mai mare decât E și apoi putem folosi acest algoritm pentru a rezolva cele mai scurte căi dintr-o singură sursă în timp de V ori E. Nu am de gând să scriu toate astea aici. O puteți vedea în note. Da? PUBLIC: Funcționează dacă graficul tău nu este simplu? JASON KU: Funcționează, deoarece graficul tău nu este simplu? Nu m-am gândit la asta. Nu vom vorbi despre grafice non-simple în această clasă, dar probabil nu pentru că aveți multe muchii. Deși în clasa noastră, dacă vorbim despre cele mai scurte căi cu o singură sursă, dacă avem mai multe muchii între două vârfuri, putem lua doar cea cu greutate minimă, deoarece nu este niciodată mai bine să le luăm pe cele mai mari. Răspunde asta la întrebarea ta? Grozav. În regulă. Deci astea sunt încălzirile noastre, acesta este scopul nostru. Trebuie să găsim un algoritm pentru cele mai scurte căi dintr-o singură sursă. Și grafice generale, grafice cu... potențial grafice cu cicluri și ponderi negative și rezolvă-le în acest timp liniar de V ori. Are sens? În regulă. Așa că mai întâi, înainte de a ajunge la algoritm, vom discuta puțin despre scurte simple - despre cele mai scurte căi în general. Dacă nu am făcut-- problema aici este ponderile negative. Cum aflăm... dacă am avut cicluri negative de greutate, se pare că există aceste probleme, pentru că am putea avea minus infinite în deltele noastre. Dar dacă nu am avea ponderi negative, aș dori să vă afirm că drumurile noastre cele mai scurte, chiar dacă există ponderi negative, vor fi simple. Nu vor repeta vârfuri. Deci acesta este primul lucru pe care ți-l vom arăta. Să vedem. Cele mai scurte căi simple. BINE. Deci, pretinde. O să-mi dau numerele de despăgubire astăzi doar pentru că voi avea multe dintre ele. Dacă distanța mea cea mai scurtă de la S la un vârf este finită, adică nu este infinită sau minus infinit - o valoare finită, există o cale mai scurtă - o cale cea mai scurtă de la S la V care este simplă. Și amintiți-vă, simplu înseamnă să nu treceți printr-un vârf de mai multe ori. În regulă. Cum vom demonstra asta? Ei bine, gândiți-vă dacă această afirmație nu a fost adevărată. Dacă fiecare cale cea mai scurtă ar conține un ciclu, în esență. A repetat un vârf. Atunci drumul meu arată cam așa. Adică, sunt niște vârfuri de-a lungul aici și apoi merg la V. Deci aici este S și apoi există un ciclu pe care îl repet, un vârf. O să numesc acest ciclu C. Acum ce știu despre această cale? Știu că are... este cea mai scurtă cale și are o greutate finită. Deci, în special, această cale - această distanță deltă nu este minus infinitul. Dar dacă acesta nu este minus infinitul, ce știu despre greutatea acestui ciclu? PUBLIC: Nu este negativ. JASON KU: Da. Nu poate fi negativ. Pentru că dacă ar fi negativ, aș putea continua în jurul acestui ciclu, iar acesta ar avea o greutate nefinită. Cea mai scurtă distanță de cale de la S. Deci știu că aceasta este... nu poate fi negativă, deci trebuie să fie 0 sau pozitivă. Dar dacă este 0 sau pozitiv și aceasta este cea mai scurtă cale-- a trecut prin acest ciclu, atunci l-aș putea elimina și acum am o nouă cale cu un ciclu mai puțin. Aș putea continua să fac asta pentru a crea o cale simplă. Deci se verifică. BINE. Deci, asta e interesant. Dacă este simplu, ce știm despre numărul de muchii dintr-un simplu drumuri scurte? Câți ar putea fi? Cât de lungă ca număr de muchii ar putea fi o cale cea mai scurtă simplă ? Dacă nu pot repeta vârfuri, pot avea cel mult vârfuri pe calea mea simplă, ceea ce înseamnă că pot folosi cel mult V minus 1 margini - postarea gardului. Deci, căile simple au cel mult V minus 1 muchii. E un lucru mic frumos pe care aș vrea să-l închid. Este o proprietate foarte frumoasă. Deci, în timp ce o cale cea mai scurtă aici ar putea avea un număr infinit de muchii, dacă cea mai scurtă distanță de cale este finită, știu că trebuie doar să verific căile care folosesc până la V minus 1 muchii. În special, aceasta este limitată în termeni de numărul de căi pe care trebuie să le iau în considerare. Este exponențial, potențial, dar cel puțin este finit. Pe de altă parte, a trebuit să verific fiecare cale posibilă din care ar putea fi infinită dacă există cicluri în graficul meu. BINE. Deci am o idee. Ce se întâmplă dacă aș putea găsi distanțe pe calea cea mai scurtă limitând numărul de margini prin care trec? Deci nu este cea mai scurtă distanță de cale de la S la V, dar să limităm numărul de muchii prin care am voie să parcurg și să vorbim despre acele distanțe de calea cea mai scurtă, doar printre căile care au cel mult un anumit număr de muchii . O să numesc această distanță k-edge. Și voi oferi doar o mică notație aici. În loc să am o deltă, voi avea o delta k aici. Asta înseamnă de câte margini sunt limitat. Deci de la S la V este cea mai scurtă cale de la S la V folosind cel mult k muchii. Scurtă-- greutate-- greutate de a. Cea mai scurtă cale, cea mai scurtă cale de la S la V folosind cel mult k margini. Și aceste noțiuni par oarecum simetrice. Dacă aș putea să calculez acest lucru pentru V minus 1, atunci -- pentru toate vârfurile, atunci dacă distanța este finită, atunci voi fi calculat cu succes cele mai scurte căi reale datorită acestei afirmații. Asta nu înseamnă că dacă asta e... nu înseamnă invers. Dacă acesta este minus infinit, dacă distanța pe calea cea mai scurtă este minus infinit, nu spune nimic despre ce este aceasta. Spune doar că cea mai scurtă cale folosind cel mult V minus 1 vârfuri, folosind cel mult V minus 1 margini ar fi oricare ar fi aceasta. Dar, într-adevăr, cea mai scurtă lungime a căii trebuie să ia în considerare un număr infinit de muchii. Deci nu ne spune prea multe despre asta. Dar pentru cei finiți o face. Merge bine. Și așadar, dacă suntem capabili să calculăm acest lucru pentru k este egal cu V minus 1 într-un grafic care nu conține cicluri de greutate negative , am fi terminat. Vă pretind o afirmație mai puternică, că dacă cea mai scurtă cale care utilizează cel mult V muchii de la s la v este mai mică decât -- strict mai mică decât delta lui V minus 1 -- totul este în indicele de aici. Practic, aceasta este cea mai scurtă distanță de cale dintre orice cale simplă și, eventual, cele care conțin și cicluri, dar cu siguranță include toate căile simple. Dacă există o cale mai scurtă către vârful meu care trece prin mai mult de V minus 1 muchii, această cale nu poate fi simplă, deoarece trece printr-un vârf de mai multe ori . În caz contrar, ar fi inclus în acest set de distanțe. Deci, dacă acesta este cazul, și am găsit o cale mai scurtă către V care folosește margini V - da, care utilizează margini V, calea nu poate fi simplă, ceea ce înseamnă că calea sau o cale de acolo conține un ciclu de greutate negativ. Deci, dacă acest lucru este adevărat, atunci știu că distanța reală pe calea cea mai scurtă de la S la V trebuie să fie minus infinitul. O să numesc un astfel de vârf martor. Dacă putem găsi un vârf care are această proprietate, adică nu ți-am arătat încă cum să calculezi aceste lucruri, dar dacă aș putea găsi un vârf V, iar acestea sunt V majuscule dacă ai necaz. Acest V este diferit de acest V, aceasta este cardinalitatea. Dacă putem găsi un astfel de vârf V, asta certifică că există un ciclu de greutate negativ în graficul nostru. Așa că îl voi chema pe V este martor. BINE. Deci, dacă această proprietate este adevărată, este un martor și cu siguranță are asta. Este posibil, crezi tu... O să-ți spun că este posibil ca un vârf să aibă o distanță infinită minus, dar să nu aibă această proprietate oprită. Probabil că aș putea să-ți dau un exemplu... Nu am unul din capul meu acum, dar este posibil. Vă puteți imagina, s- ar putea să nu existe o cale care să meargă la un vârf pe un ciclu de greutate negativă care să treacă prin V exact V muchii. S- ar putea să treacă prin mai multe margini, una mai scurtă. Deci această ecuație ar fi inegalitate și nu ar certifica că acest lucru este adevărat. Dar vă pretind că, dacă un vârf are această proprietate, dacă este cea mai scurtă distanță de cale minus infinit, atunci trebuie să fie accesibil de la un martor. Deci asta e pretenția. Dacă delta S, V este minus infinit, atunci V este accesibil de la un martor. Accesibil de la un vârf care are această proprietate... care are această proprietate. Și dacă este accesibil de la ceva care are calea cea mai scurtă minus infinit, atunci pot lua acea cale care merge la vârful meu accesibil și aceasta este, de asemenea, calea minus infinit. BINE. Deci, cum demonstrăm asta? Ei bine, haideți să luăm în considerare... să vă spun o afirmație oarecum mai puternică pe care o vom demonstra în schimb. Este suficient să demonstrăm că fiecare ciclu negativ de greutate conține un martor. Dacă trebuie să demonstrăm că, atunci fiecare vârf cu această proprietate, fiecare vârf cu această proprietate este accesibil prin definiție dintr-un ciclu de greutate negativă. Deci, dacă putem demonstra că fiecare... dovedește că fiecare ciclu negativ de greutate conține martori. Dacă putem demonstra că fiecare ciclu de greutate negativă conține un martor, atunci fiecare vârf accesibil de la unul dintre acei martori -- în special, accesibil din ciclul de greutate negativă -- are cea mai scurtă distanță minus infinitul și asta ar trebui să dovedească afirmația. Acest lucru trebuie să fie accesibil dintr-un ciclu de greutate negativ. Și așadar, dacă demonstrăm că ciclurile de greutate negative conțin martori, atunci toate aceste vârfuri sunt accesibile de la un martor. OK, grozav, grozav. Mă încurc acolo pentru o secundă. BINE. Deci, să luăm în considerare un ciclu de greutate negativ. NG. Iată un ciclu de greutate negativ direcționat. Amintiți-vă. Acesta va fi ciclul meu de greutate negativă C. Toată suma marginilor din acest lucru, greutățile au greutate negativă. Și voi avea un pic de notație - dacă am un vârf V aici, voi spune că predecesorul său în ciclu, îl voi numi doar V prim. Asta e doar o notație. În regulă. Deci, dacă am calculat aceste distanțe cu calea cea mai scurtă până la fiecare vârf din graficul meu, distanța cea mai scurtă care trece prin cel mult V vârfuri și cea mai scurtă distanță prin cel mult V minus 1 vârfuri, atunci știu că este valabil următorul lucru. Delta V care merge de la S la V pentru orice vârf din ciclul meu nu poate fi mai mare decât delta V minus 1 de la S la U plus greutatea -- îmi pare rău, nu U-- V prim, predecesorul său, plus greutatea care trece de la predecesorul vârfului meu. De ce este asta? De ce este asta? Pentru că aceasta este greutatea unui vârf - aceasta este greutatea - cea mai scurtă distanță de cale până la predecesorul meu folosind o margine mai puțin. Și astfel, aceasta este în special greutatea unei căi care utilizează muchii V. Deci, dacă aceasta este cea mai scurtă distanță de cale, aceasta trebuie să o limiteze cel puțin... cel mult. Da? PUBLIC: Asta este inegalitatea triunghiului? JASON KU: Aceasta este o afirmație a inegalității triunghiului, mulțumesc. În regulă. Deci, da, aceasta este doar prin inegalitatea triunghiulară. BINE. Acum ceea ce putem spune este că să luăm această ecuație însumată peste toate nodurile din ciclul meu. Așa că voi adăuga aici o însumare a tuturor nodurilor din ciclul meu al întregii chestii. O să fac asta puțin mai îngrijit. Însumarea deltei, nu d. Delta V S, V. Cred că nu am nevoie de aceste paranteze deschise. Egal-- sau mai mic sau egal cu suma V și C din delta V minus 1 V prim. Și aici, însumez V și C, iar aceasta este doar notația mea pentru predecesor. Și apoi o să însumez greutățile din ciclul meu V și C. Acestea sunt suma greutăților din ciclul meu. Ei bine, ce știu despre acest ciclu? Aceasta este doar greutatea lui C. Greutatea lui C... este un scris de mână îngrozitor. C, ce știu despre greutatea ciclului? Este negativ. Deci, acesta este mai mic decât 0, ceea ce înseamnă că dacă elimin asta, aceasta trebuie să fie o egalitate strictă. Dar dacă suma tuturor acestora este strict mai mică decât suma tuturor acestora, nu putem avea niciunul dintre vârfurile din graficul meu care să satisfacă-- să nu satisfacă această proprietate. Dacă nu toți sunt martori, atunci acest lucru este mai mare decât acest lucru - cel puțin la fel de mare ca acest lucru pentru fiecare vârf din ciclul meu, ceea ce este o contradicție. Deci, afirmația este valabilă, dacă avem o distanță infinită negativă pe calea cea mai scurtă, atunci V este accesibil de la un martor. Așa că ne este suficient să găsim toți martorii, să găsim toate vârfurile accesibile de la martori și apoi să le marchem ca minus infinit. Are sens? BINE. Deci, acum suntem în sfârșit capabili să ajungem la algoritmul nostru. Bellman-Ford. Și ceea ce vă voi arăta astăzi este puțin diferit de ceea ce este prezentat în mod normal ca Bellman-Ford. Algoritmul original Bellman-Ford face ceva puțin diferit. Și pentru că face ceva puțin diferit, despre care vom vorbi la final, este puțin mai păros de analizat. Vă voi arăta o modificare care este puțin mai ușor de analizat și care are această proprietate frumoasă că vom putea folosi algoritmul pentru a ne oferi un ciclu de greutate negativă dacă există. Deci, vom spune că acesta este poate un Bellman-Ford modificat. Iar ideea aici este să faci un asociat de vârf - să faci multe versiuni ale unui vârf. Și vreau ca această versiune a vârfului să corespundă dacă am venit aici folosind 0 muchii, 1 muchie, 2 muchii, 3 muchii -- Am o versiune de vârf diferită a vârfului pentru fiecare dintre acestea -- pentru o cale care trece prin , cel mult, un anumit număr de muchii. BINE. Deci aceasta este o idee numită duplicare grafică. Idee, duplicare grafică. Și aceasta este o tehnică foarte comună pentru rezolvarea problemelor legate de grafice. Pentru că, în esență, ceea ce trebuie să fac este să stochez informații. Dacă am versiuni diferite ale unui vârf, pot avea acel vârf să corespundă atingerii acelui vârf într-o stare diferită. Deci asta vom face aici. Ideea aici este să facem V plus 1 niveluri - practic vârfuri duplicate în graficul nostru - unde vârful Vk la nivelul k reprezintă atingerea vârfului V folosind cel mult k muchii. OK, deci această definiție pare similară cu ceea ce facem noi aici. Dacă avem vârfuri care au această proprietate, atunci căile lor cele mai scurte din acest nou grafic ar putea corespunde acestor k distanțe de margine. Și într-adevăr, numele jocului aici este să calculăm aceste două pentru fiecare vârf, pentru că atunci putem-- atunci dacă d este finit, delta este finit, atunci acest tip va fi lungimea drumului nostru cel mai scurt. Și dacă sunt diferiți, acesta va fi un martor și putem explora din el. Deci, și dacă conectăm marginile de la un nivel la doar niveluri superioare, practic niveluri cu un k mai mare, atunci acest grafic va fi un DAG. Vai. Asta e tare. De ce e mișto? Pentru că am văzut cum să rezolvăm cele mai scurte căi dintr-o singură sursă într-un DAG și timp liniar. Acum, acest grafic pe care îl vom construi va avea V plus 1 niveluri. Deci ar fi putut... graficul nostru explodează de V ori. Vom face asta într-o secundă. Voi fi mai precis cu ceea ce vreau să spun acolo. Dar dacă înmulțim graficul nostru V plus de 1 ori, atunci dimensiunea graficului nostru este acum de V ori mai mare. Asta nu... nu e atât de greu de crezut. Dar dacă am făcut graficul nostru de V ori mai mare și am rulat un algoritm de calea cea mai scurtă în timp liniar în raport cu acel grafic, atunci acel grafic are ceva ca dimensiunea V ori V plus dimensiunea E. Pare cunoscut, poate? Acesta este timpul de funcționare. Deci, dacă putem găsi un algoritm care rulează în acel timp de rulare, putem ajunge la V ori E. Deci, să încercăm să facem asta. Iată transformarea pe care o voi arăta. Vă voi arăta mai întâi cu un exemplu. Iată un exemplu de grafic direcționat care conține un ciclu de greutate negativ. Poate cineva să-mi găsească? bcd. Are o greutate de minus 4 plus 3 minus 1. Are o greutate totală de minus 2. Deci, acesta este un ciclu de greutate negativ. Deci, pentru a lua cele mai scurte căi de la a, voi dori să spun la sfârșitul algoritmului meu, acesta ar fi mai bine 0 și toate acestea ar fi mai bine minus infinitul. Deci asta vreau în algoritmul meu. Deci, care va fi algoritmul meu? Voi face V plus 1 copii ale acestui grafic și îl voi întinde într-un fel. BINE. Deci aici, am V 0, 1, 2, 3, 4 -- sunt patru vârfuri în graficul meu. Deci acestea sunt 1, 2, 3, 4, 5 copii ale graficului meu. Am o versiune de vârf a pentru fiecare dintre acele copii, o versiune de vârf b pentru fiecare dintre acele copii, c și d și cetera. Deci am această grilă frumoasă de vârfuri. Și nu voi pune margini într-un strat, într-un nivel. Pentru că atunci... Adică, acest grafic are cicluri. Și nu vreau cicluri în graficul meu. Ceea ce voi face în schimb este pentru fiecare muchie din graficul meu original -- de exemplu, muchia de la a la b, o voi conecta la b la nivelul următor. Deci, a0 este conectat la b1 cu o greutate de margine de minus 5, la fel ca în original. Și o să fac asta pentru fiecare muchie din graficul meu și o voi repeta până la capăt. În plus, voi adăuga o margine cu greutate zero de la a0 la a1 sau de la fiecare vârf până la capătul liniei. Toate acestea sunt muchii cu greutate zero care corespund cu... Nu voi traversa o muchie, voi rămâne doar la acest vârf. Asta ne va permite să simulăm această condiție de cel mult k margini. Acum, dacă aruncați o privire la căile din acest grafic de la a0, vârful nostru de pornire , în mod clar niciunul dintre celelalte vârfuri din acel nivel nu este accesibil de la a0, așa cum ne dorim. Deoarece distanța pe calea cea mai scurtă până la oricare dintre aceste vârfuri folosind cel mult 0 muchii ar trebui să fie infinită. Nu pot ajunge acolo în 0 margini. Dar apoi orice cale din acest grafic care utilizează cel mult k muchii va corespunde unei căi de la a0 la un vârf din acel nivel, nivelul corespunzător. Deci, de exemplu, dacă aș avea a-- dacă aș căuta căile 2b folosind cel mult trei muchii, orice cale-- o cale de la a0 la b3 în acest grafic ar corespunde unei căi din acest grafic care utilizează cel mult trei muchii . deci Să găsim o astfel de cale. Deci, mergând de la a0, b1, rămâneți la b1-- rămâneți la b, îmi pare rău. Da, este o cale care folosește mai puțin de trei muchii sau cel mult trei muchii. Dar există o altă cale aici. Unde este? Trecând de la a, a, a la b... OK, nu este una atât de interesantă. Este aceeași cale. Așa că s-ar putea să am mai mult de o cale înăuntru care corespunde unei căi de acolo, dar pretenția mea este că orice cale de aici corespunde unei căi de aici. Deci, ce este o cale de lungime? 3, asta nu este banal. Da, de la a la c la d la b. Deci de la a la c la d la b. Da, asta e o cale. Și practic, pentru că am construit asta astfel încât marginile să se miște mereu de la un nivel la altul, pe măsură ce traversez aceste margini, schimb mereu nivelurile. Da? PUBLIC: Dar graficul meu original nu are aceste auto-bucle cu greutate 0. JASON KU: Da. Graficul meu original nu are o margine de la a la a. Este adevărat. Folosesc aceste margini pentru a corespunde cu... Mă hotărăsc să nu iau o margine. Nu este că aș lucra aici, ci doar stau acolo pentru o stare. Și asta îmi va permite să obțin asta la cele mai multe margini. În regulă. Deci, acesta este constructul grafic. Sper că înțelegeți că am făcut aceste straturi în V. Acesta este V. Și un vârf -- am făcut V copii ale fiecărui vârf și le-am conectat folosind muchii în acest fel. BINE. Deci, primul pas al lui Bellman-Ford este construirea acestui grafic. Deci, Bellman-Ford, construiți G prim așa cum este descris mai sus. Are câte vârfuri? V ori V plus 1. V ori V plus 1 vârfuri. Și câte margini? Ei bine, am o margine pentru marginea de ieșire pentru fiecare vârf care corespunde doar rămânerii în același loc. Deci sunt vârfuri V pătrat -- mă refer la margini. Și apoi am o margine-- pentru fiecare muchie din graficul meu, am-- îmi pare rău. Am un V minus 1... scuze. Doar V. Am V muchii pentru fiecare muchie din graficul meu. Deci asta înseamnă... deci acesta este numărul de vârfuri. Și de V ori V plus V ori E, acesta este V V plus E. Bine, cool. Deci atâtea margini am. Deci construit în acest fel, este un DAG. Dacă avem margini care merg la niveluri crescătoare, atunci acest lucru nu poate avea cicluri, pentru că altfel ar însemna că ar exista o margine îndreptată înapoi. Și nu am construit niciuna dintre acestea. În regulă. Deci construim acest grafic G prim. Putem face asta în timp liniar cu privire la aceste lucruri. Trec doar prin toate marginile, fac aceste margini și fac aceste vârfuri. Nu este nevoie de nimic... O fac doar naiv. Corect, pot face asta în timp V ori V plus E asimptotic. BINE. Acum rulez DAG relaxare, algoritmul nostru frumos pe care l-am avut data trecută, de la... înăuntru era a0. O să spun că este S0, sursa noastră. Vârful nostru sursă. Cele mai scurte căi cu o singură sursă. Astfel încât să calculez delta de la S0 la Vk pentru toate k și-- ce este? De la 0 la V. Asta face cele mai scurte căi cu o singură sursă. Acesta calculează pentru mine această distanță de la sursa mea - de la o sursă la orice alt vârf din grafic. Și astfel, în special, le primesc. Ei bine, asta sunt toate. Apoi, pentru fiecare vârf V, setați-- lucrul pe care îl voi întoarce, valoarea d, de la S la V, egală cu distanța pe calea cea mai scurtă pe care am obținut-o de la relaxarea DAG la un anumit vârf. V V minus 1. De ce fac asta? O setez să fie cea mai scurtă distanță de cale până la tipul din al doilea rând aici sau coloana din graficul meu modificat. Speranța este că această distanță din DAG-ul meu să corespundă acestei distanțe din graficul meu original. Distanța până la V folosind cel mult V minus 1 muchii. Deci aceasta este afirmația... aceasta este o afirmație pe care o vom demonstra într-o secundă. O voi scrie doar ca să avem... doar pentru a ne continua șirul gândurilor. Revendicare, delta S0 Vk este egală cu delta k, distanța k la margine, de la S la V. Asta vrem să pretindem. Atunci asta ar... ce ar însemna asta, atunci? Asta ar însemna că setez corect aici distanța pe calea cea mai scurtă pentru toate nodurile ale căror distanțe sunt finite. Grozav. Adică, le-am stabilit valori pentru lucruri în care nu sunt finite, unde sunt și minus infinit, dar în special le-am stabilit corect pe acelea dacă sunt finite. BINE. Deci ultimul lucru pe care trebuie să-l facem este să ne ocupăm de aceste vârfuri minus infinit. Dar noi știm cum să facem asta. Ne uităm doar la martori. Deoarece am calculat această valoare pentru k egal cu V egal cu V minus 1, iar dacă această afirmație de acolo este adevărată, atunci acele distanțe pe calea cea mai scurtă sunt aceleași cu aceste distanțe pe calea cea mai scurtă. Și putem doar, pentru fiecare vârf, să comparăm aceste lucruri. Dacă acest lucru este satisfăcut, avem un martor. BINE. Deci pentru fiecare martor U și V unde delta S0 U V este mai mică decât, strict, S0 U V minus 1 -- asta este definiția unui martor aici, închideți parantezele. Apoi, pentru fiecare vârf V accesibil din U set-- îmi pare rău, d, este ceea ce returnăm, d din S, V egal cu minus infinitul. Acesta este sfârșitul algoritmului. Practic, îi caut pe toți martorii. Pentru fiecare martor, găsesc toate nodurile accesibile din acesta și le setez la minus infinit, așa cum am argumentat mai înainte. BINE. Deci, rămâne să dovedim această afirmație. Cum demonstrăm această afirmație? Ei bine, putem induce pe k. Este acest lucru adevărat pentru k este egal cu 0? Da. Am discutat deja aici când vorbim despre pasul nostru de inițializare sau despre ce face relaxarea DAG. Aceasta va fi cea mai scurtă cale de la acest tip la toate aceste vârfuri. Acestea nu sunt accesibile de aici, deci acestea sunt infinite. Și acela este 0. Deci cazul de bază - deci induceți pe k caz de bază, k este egal cu 0? Verifica. Asta-i bine. Acum noi-- în pasul nostru inductiv , să aruncăm o privire la distanța pe calea cea mai scurtă de la 0-- de la S0 la V de k prim pentru un k prim. Și presupunerea este că ipoteza inductivă este că această distanță este distanța de la margine k pentru toate k prime mai mici decât-- Adică toate k mai mici decât k prim. Ei bine, prin definiția unei căi cele mai scurte, acesta este vârfurile minime globale de intrare ale celei mai scurte căi de la S0 la U de k prim minus 1 plus greutatea muchiei de la U de k prim minus la Vk prim pentru toate Uk prime minus 1 în adiacențele, adiacențele de intrare ale lui Vk prim. OK, ce înseamnă asta? Spun doar în graficul meu G prim, o cale cea mai scurtă către acest vârf trebuie să treacă mai întâi prin un vârf din stratul dinaintea acestuia, care este unul dintre acestea. Și în special, sunt conectat doar la lucruri adiacente mie. Asta e tot ce se spune. Trebuie să trec prin acel vârf și să iau cea mai scurtă cale către unul dintre acele vârfuri anterioare. Acum, actualitatea, aceste adiacente, le-am construit astfel încât să fie similare cu adiacentele din graficul meu original, în plus față de o muchie care vine de la vârful meu original, de la vârful V. Deci, acesta este același cu minimul acestui set delta S0. Același lucru. Plus W U, V pentru toate U din adiacențele adiacente-- de intrare ale vârfului meu original. Pe lângă încă un termen. Care este celălalt termen? Acestea sunt toate lucrurile care corespund marginilor mele inițiale, dar am și acea margine care vine de la V înainte. Așadar, aceasta este-- voi uni-- uniune-- uniți asta cu delta S0 V din k prim minus 1. Îngrozitor. Cred că mai e unul aici. Acesta este S0 din k prim minus 1. Nu o voi rescrie. OK. Apoi, prin inducție, acest lucru și acest lucru trebuie să fie cele mai scurte căi de margine folosind k minus 1 vârfuri. Și atunci aceasta este doar afirmația a ceea ce calea cea mai scurtă ar trebui să folosească cel mult k muchii prime care merg de la S la V. Deci, aceste lucruri sunt aceleași pe care le-am susținut. Da, verificați. Bine. Și atunci nu este așa -- este un fel de salt trivial, atunci, să spun că, la sfârșitul lui Bellman-Ford, acești tipi... îmi pare rău, lucrurile pe care le întoarcem, acești băieți, sunt distanțele pe calea cea mai scurtă , pentru că aici, dacă sunt finite, le setăm la cea mai scurtă distanță. distanța traseului; și dacă sunt minus infinit, acel invariant înseamnă că aceste lucruri corespund exact acestei afirmații de aici. Este un martor. Și apoi găsind toate vârfurile accesibile de la acești martori, le setăm pe toate infinite să fie minus infinit după dorință. OK, deci care este timpul de rulare al acestui lucru? Ei bine, a trebuit să construim acest grafic, așa că a trebuit să luăm acel timp. Am rulat relaxarea DAG, care durează același timp. Pentru fiecare vârf, am făcut comanda V la lucru. Și apoi pentru fiecare martor, câți ar putea fi? Și majoritatea, V. Verificarea accesibilității fiecărui vârf, asta se poate face în cât timp? Comanda E ora. Pentru că nu trebuie să luăm în considerare lucrurile care nu sunt legate de S-- sau care nu sunt legate de martor. Deci acest lucru ia ordine de V ori E lucru. Deci suntem limitați de acest timp necesar pentru a construi graficul original și de afirmația pe care am avut-o înainte, care durează de V ori E timp. BINE. Deci, acesta este Bellman-Ford. O să te las doar cu două pepite. În primul rând, cea mai scurtă cale, dacă este pentru orice martor... să presupunem că avem un martor aici. Am vreun martor aici? Nu le-am completat pe toate. Dar există vreun vârf pe acest ciclu care trece prin cine are calea cea mai scurtă? Acesta trece prin patru vârfuri care sunt mai mici decât oricare altele. BINE. Pot trece de la a la c la b la d la b la c. Și puteți elabora acest algoritm... Îl am în note pe care le puteți arunca o privire. Aceasta va avea de fapt o cale mai scurtă pentru vertex-- îmi pare rău. Va avea o cale mai scurtă pentru vârful b. de la a la b la c la d la b. Mulțumesc. Este o cale de lungime 4, de patru margini. Care are o cale mai scurtă decât orice cale care are mai puține margini. În special, există o singură altă cale către b care folosește mai puțin de patru -- există alte două căi. O cale de lungime-- care are o margine, care are greutatea minus 5, și o cale-- această cale care are greutatea 9 minus 1 este 8. În timp ce această cale, minus 5, minus 4, 3, minus 1 are minus 10 plus 3 este minus 7, care este mai scurt decât minus 5. Deci b și d sunt un martor. Și dacă ne uităm de fapt la acea cale prin acest grafic, mergând de la a la b la c la d înapoi la b, vedem că există un ciclu de pondere negativă în acest grafic. b la c la d la b. Și într-adevăr, acesta este întotdeauna cazul martorilor noștri. Puteți vedea o dovadă în acest sens în note și puteți vedea în recitare o mică optimizare a spațiului pentru a ne face să nu trebuie să construim întreg acest grafic din mers, ci de fapt să folosim spațiul de ordine V în timp ce merg. BINE. Deci, acesta este Bellman-Ford. Scuze că am întârziat puțin.