[SCRÂTIT][FOȘIT][CLIC] JASON KU: Bun venit, tuturor, la prelegerea noastră 14 din 6.006. Aceasta este ultima noastră prelegere despre algoritmii grafici, în special, ultima prelegere pe care o vom avea despre cele mai scurte căi ponderate. Dar vom vorbi despre o problemă ușor diferită astăzi, diferită de cele mai scurte căi cu o singură sursă. Vom vorbi despre cele mai scurte căi ale tuturor perechilor. Dar mai întâi, să revizuim algoritmii noștri cu cea mai scurtă sursă. Am avut BFS, DAG relaxare, Dijkstra, pe care l-am văzut data trecută, care se apropie destul de mult de liniar. V log V plus E este destul de aproape de liniar. Este mult mai aproape de liniar decât algoritmul general pe care îl avem pentru a rezolva cele mai scurte căi cu o singură sursă, și anume, Bellman-Ford, care este puțin mai mult ca pătratic. Aceasta este ca diferența dintre -- pentru graficele rare, aceasta este ca diferența dintre sortare, folosind sortarea prin inserție și n pătrat și sortarea îmbinată în N log N, de exemplu. Vom obține de fapt un bonus destul de mare pentru dimensiuni mari de intrare folosind Dijkstra atunci când putem. Astăzi, ne vom concentra pe această nouă problemă numită cele mai scurte căi ale tuturor perechilor. Nu este chiar complicat. În loc să avem o singură sursă, dorim în esență , având în vedere o intrare - acesta este graficul nostru ponderat, unde avem un grafic V, E și avem o funcție de greutate de la margini la numere întregi. Acesta este graficul nostru general ponderat. Vrem ca rezultatul nostru să fie ceva de genul, cea mai scurtă distanță de cale de la u la v pentru fiecare u și v din setul nostru de vortex. Asta vrem să ne întoarcem. Acum, există o avertizare aici că, dacă există un ciclu de pondere negativă în graficul nostru - cu alte cuvinte, dacă oricare dintre aceste delta u, v este minus infinitul, există un ciclu de rată negativă în graficul nostru. Deci, cu excepția cazului în care, cred... sau avort dacă G conține un ciclu de greutate negativ. Deci, de fapt, nu ne vom îngrijora cu privire la ciclurile negative de greutate în cursul de astăzi. Dacă avem un grafic, acesta ar putea avea ponderi negative. Acestea sunt orice numere întregi. Ar putea include margini negative de greutate. Dar atâta timp cât toate distanțele noastre de cale sunt mărginite de jos, niciuna dintre ele nu este infinit negativ, nu avem cicluri negative de greutate , atunci vreau să scoți toate aceste distanțe cele mai scurte de cale. Acum, în special, această ieșire ar putea-- oricare dintre aceste ieșiri trebuie să aibă dimensiunea teta de V pătrat. Pentru că pentru fiecare pereche de vârfuri, trebuie să vă întorc un număr, sau infinit, sau minus infinit sau ceva de genul ăsta. Dar nu avem de-a face cu un caz cu minus infinit. Ieșirea ar putea avea dimensiune - acesta este un theta aici. Are dimensiunea V pătrat. Dar, în special, este cel puțin V pătrat pentru că trebuie să dau un număr pentru fiecare pereche de vârfuri. Și deci nu am putea spera la timp liniar în dimensiunea acestui grafic pentru această problemă, nu? Cele mai scurte căi cu o singură sursă , pentru anumite versiuni ale problemei, trebuie să citim graficul. Și deci trebuie să folosim timpul liniar. Dar în această problemă, rezultatul nostru are dimensiune pătratică în numărul de vârfuri. Deci, într-un fel, nu putem face mai bine decât asta. Nu putem face mai bine decât pătratica. Și de fapt, care este o modalitate prin care am putea rezolva cele mai scurte căi ale tuturor perechilor folosind lucruri pe care le- am făcut deja în această clasă? De aceea am pus acest slide aici. Da, am putea doar să rezolvăm un algoritm cu cele mai scurte căi de la fiecare vârf din graficul meu. Pare un lucru stupid de făcut. Este aproape forță brută pe vârfuri. Dar cu siguranță este o modalitate prin care am putea rezolva această problemă, în timp polinomial. Și cu siguranță l-am putea rezolva în ordinea V pătrat E timp, folosind Bellman-Ford. Facem doar V pași de Bellman-Ford și ne ocupăm de un grafic pe orice set de vârfuri. Putem face mai bine decât asta. Putem face mai bine decât atât pentru graficele care sunt speciale într-un fel. Putem face V ori V plus E, V ori liniar. Dacă ponderile noastre sunt pozitive și mărginite, putem folosi BFS V ori. Sau dacă graficul nostru nu are cicluri, am putea folosi relaxarea DAG V ori. Sau dacă graficul nostru ar avea greutăți de margine nenegative, am putea obține, practic, V pătrat log V plus V ori E. Și asta de fapt nu este rău. În grafice rare, aceasta este ceea ce ne-ar oferi Bellman-Ford. Dar dacă am avea Dijkstra, de exemplu, dacă am avea toate greutățile pe marginea pozitivă-- sau nenegative, îmi pare rău, am putea obține V pătrat log V plus V, E timp. Aceasta este de V ori Dijkstra. OK, deci cum se compară acești timpi de funcționare? Este de V ori Bellman-Ford. Aceasta este de V ori Dijkstra. Haideți să facem o idee despre această separare aici. Dacă am avea un grafic rar în care V este mărginit în sus de numărul de vârfuri, acesta arată ca V pătrat log V. Acesta arată ca V cub. Și trebuie să petrecem cel puțin timp V pătrat. Deci, de fapt, acesta este foarte aproape de liniar în dimensiunea graficului, doar cu un factor de log, la fel cum ar presupune sortarea. Și acesta ar avea un factor liniar. În graficul rar, acesta ar fi un factor liniar mai rău decât acesta, în loc de un factor logaritmic - din nou, această separare liniară de log. Nu vrem să fim nevoiți să facem acest timp de funcționare dacă nu trebuie. Acesta este numele jocului. Și într-adevăr, tot ceea ce vom face în această prelegere este să încercăm să rezolvăm cum putem face acest timp de rulare mai rapid făcând ceva puțin mai inteligent decât rulând un algoritm de calea cea mai scurtă dintr-o singură sursă de la fiecare vârf. Cum vom face asta? Ei bine, am putea... să vedem. Ce facem? Dreapta. Ideea aici, dacă am avea un grafic - ar trebui ca graficul meu să fie direcționat sau nedirecționat? Nu sunt sigur. Să vedem dacă putem face un grafic direcționat. OK, deci iată un grafic direcționat. De ce nu-mi pasă de graficele nedirecționate? Imi poate spune cineva? Da, pentru că... nu-mi pasă de graficele nedirecționate pentru că, dacă aș avea un grafic nedirecționat, aș putea detecta dacă am avut cicluri negative de greutate în timp constant... Îmi pare rău, în timp liniar. Aș putea doar să verific fiecare muchie, să văd dacă are pondere negativă, deoarece o muchie negativă , o muchie nedirecționată este un ciclu de pondere negativă. Așa că aș putea doar-- dacă are ponderi de margine negativă, aș putea reveni în timp liniar pe care îl are și pot avorta. Sau are doar greutăți pozitive și încă pot folosi Dijkstra. Deci totul e bine. Așadar, ne preocupă doar nevoia de a rula Bellman-Ford pe grafice direcționate care pot avea greutatea marginii negative . OK, deci iată un grafic. Să vedem. Acesta este un grafic pe care îl vreau? Sigur. Să presupunem că avem acea direcție și această direcție. Să presupunem că avem un grafic dirijat ca acesta. Și să spunem că acesta este s. Aceasta este sursa noastră. Și avem ponderi fiind 2-- ne pare rău, ponderi fiind 4, 1, 1, 2, 2, 2, 2. Deci acesta este un exemplu de grafic pe care ar putea dori să rulăm cele mai scurte căi ale tuturor perechilor. Poate că avem și ponderi negative în acest grafic. În special, acesta are un ciclu de greutate negativ. Nu vreau cicluri de greutate negative, așa că voi face acest 0. Deci acest grafic nu are cicluri de greutate negative. Grozav. Este adevărat, grozav. În regulă, deci iată un exemplu pe care am putea dori să calculăm cele mai scurte căi. Nu există s în cele mai scurte căi ale tuturor perechilor. Dar voi vorbi despre câteva căi cele mai scurte de la s în următorul meu argument, așa că voi eticheta acel vârf ca s. OK, afirmația -- abordarea pe care o vom face, vom încerca să luăm un grafic care are ponderi de margine negativă , grafic direcționat. Nu știm dacă are cicluri negative sau nu încă. Dar dorim să calculăm cele mai scurte căi ale tuturor perechilor, nu în acest timp de rulare, ci în acest timp de rulare. Cum am putea face asta? Ei bine, poate este posibil să putem schimba greutatea fiecărei margini, astfel încât să fie toate pozitive, dar cele mai scurte căi sunt păstrate. Deci, practic, dacă o anumită cale - cum ar fi OK, cea mai scurtă cale de la s la t aici este 1, 2, 3. Aș putea schimba greutățile marginilor în acest grafic. Să spunem, de exemplu, dacă aș schimba 1 la 0 aici, asta ar face totuși calea cea mai scurtă. Nu am făcut... Am reponderat graficul. Cele mai scurte căi trebuie să fie aceleași în acest grafic. Dar acum... îmi pare rău. Da, aceasta nu este cea mai scurtă cale. OK, o să fac minus 2, apoi pe ambele 2, și cred că asta 4. Omule, chiar ar fi trebuit să-mi fac exemplul înainte. OK, deci aceasta încă nu are cicluri negative de greutate. Are o margine negativă de greutate. Dar această cale este mai lungă decât această cale. Deci, când acesta era 1, acesta avea lungimea de 3, care era mai scurtă decât această cale. Aceasta este lungimea 4. OK, cool. Deci aceasta este cea mai scurtă cale de la s la t. Aș putea schimba ponderile în acest grafic, de exemplu, schimbând 2 la 3 și 1 la 0. Asta a schimbat ponderile în graficul meu, dar cele mai scurte căi rămân aceleași. Deci, poate există o modalitate prin care aș putea să-mi reponderez marginile, astfel încât cele mai scurte căi să rămână la fel, cele mai scurte căi să fie păstrate. Așa că am de gând să pun asta înapoi acolo unde a fost. Așadar, idee-- faceți ponderile marginilor nenegative, păstrând în același timp căile cele mai scurte. Cu alte cuvinte, doar reponderați muchiile aici, astfel încât cele mai scurte căi din G-- acesta este G-- după ce reponderăm, vor merge la un grafic G prim, cu aceeași structură combinatorie, doar cu greutăți de margine diferite . Și vrem căile cele mai scurte - vrem ca aceste ponderi să fie toate nenegative. Și vrem căile cele mai scurte, dacă există o cale mai scurtă în G, aceasta continuă să fie cea mai scurtă cale în graficul reponderat. Acesta este scopul pentru azi. Dacă putem face acea transformare și acest lucru nu este negativ, atunci am terminat. Am terminat pentru că putem rula Dijkstra de V ori pe noul grafic, obținem cele mai scurte distanțe de traseu, construim un arbore de cale cea mai scurtă de la acele distanțe și apoi traversăm acel arbore în graficul original și calculam cele mai scurte căi de-a lungul acelui arbore. Deci asta e pretenția. Afirmați-- putem calcula distanțe în G-- așa că vom restricționa G prim pentru a avea greutăți de margine nenegative. Dacă avem un astfel de G prim cu greutăți de margine nenegative, putem calcula distanțe în G de la distanțe în G prim în V ori V plus E, care este mai mic decât timpul nostru de rulare Dijkstra. Acesta este timpul nostru de funcționare Dijkstra. Și acesta este mai mic decât atât. Deci ar fi bine, nu? Ce facem? Avem noul nostru grafic G prim. Are toate greutățile de margine pozitivă, așa că parcurgem cele mai scurte căi în toate perechile doar rulând Dijkstra de V ori. Și apoi, pentru fiecare vârf s, avem un arbore cu calea cea mai scurtă către toate lucrurile la care este conectat. Putem privi acea cale în G. Acesta este același grafic comun [INAUDIBIL], doar cu greutăți de margine diferite. Ne putem uita la același copac. Nu voi putea desena exact același copac aici. Dar ceea ce pot face este să pot doar BFS sau DFS de-a lungul acestui arbore. Și de fiecare dată când am o margine, deoarece fiecare dintre acestea este cea mai scurtă cale din acest arbore, pot doar să calculez de fiecare dată când parcurg o margine care este cea mai scurtă distanță a căii sale în G în timp liniar pentru acel vârf pentru acel s anume. Fac asta peste toate s-urile și primesc acest timp de funcționare. Deci acesta este scopul aici. În regulă, așa că am vrut mai întâi să găsim... am vrut să facem ca ponderile marginilor să nu fie negative, păstrând în același timp căile cele mai scurte. Pentru că dacă am putea face asta, am putea rezolva problema noastră inițială a celor mai scurte căi ale tuturor perechilor. Deci aceasta este schița dovedită. Dar cum putem face asta? Dar cum? Nici măcar nu pare că acest lucru ar putea fi posibil, în general. Cum pot să reponderez marginile și să mențin că arborii cu calea cea mai scurtă sunt aceiași? Asta pare greu de făcut. Și în special, dacă există un ciclu de greutate negativ în acest grafic, este imposibil de făcut. Deci, susține-- nu este posibil dacă G conține un ciclu de greutate negativ . OK, punctul de exclamare este doar comentariul meu aici. Deci, dacă G conține un ciclu de greutate negativ, atunci în special, cea mai scurtă distanță de cale sau o cale cea mai scurtă din G -- dacă acesta este G, să presupunem că avem un ciclu de greutate negativ direcționat aici. În special, calea cea mai scurtă de la acest vârf de pe ciclu la acest vârf de pe ciclu, care este calea sa cea mai scurtă? Este infinit. Cea mai scurtă cale este infinită în jurul acestui ciclu. Pur și simplu continuați să înconjurați ciclul iar și iar și iar pentru că are o greutate negativă. Greutatea lui C este mai mică decât 0, strict. Asta este un ciclu negativ de greutate. OK, deci calea cea mai scurtă - o cale cea mai scurtă de la s la t are lungime infinită și, în special, nu este simplă. Totuși, deci calea cea mai scurtă de la s la t nu este simplă. Dar, așa cum am demonstrat în ultima prelegere, care sunt cele mai scurte căi dintr-un grafic cu ponderi nenegative? Sunt simple, nu? Pentru că sunt doar copaci cu calea cea mai scurtă. Deci asta e o contradicție. Deci acest lucru nu este posibil. Deci, având în vedere un grafic cu ponderi negative, dar fără ciclu negativ, încă nu este clar cum am putea găsi o astfel de reponderare a graficului. Putem face asta? Ei bine, vom exploata o mică idee aici. Cum putem transforma greutățile unei căi? Ei bine, cum... ce este o... o idee prostească, am această idee prostească. Dacă nu vreau greutăți de margine negativă în acest grafic... ugh, asta e dezordonat în spate. Aveți ponderi de margine 1, minus 2, 0, 1, 4, 5 și 1. Există o singură pondere de margine negativă aici. Ce se întâmplă dacă tocmai aș adăuga un număr mare sau, în special, negativul celei mai mici muchii din graficul meu la fiecare muchie din graficul meu? Apoi voi avea un grafic cu ponderi non-negative. Fantastic. De ce nu este o idee bună? Ei bine, în special, dacă am făcut asta la acest grafic, dacă am adăugat 2 la fiecare muchie, greutatea acestei căi, care era cea mai scurtă cale, s-a schimbat de la greutatea 3 la greutatea 9, pentru că am adăugat 2 pentru fiecare muchie. Dar această cale, care nu era cea mai scurtă cale din graficul original -- avea o greutate de 4 -- a crescut doar cu 2. Acum aceasta este cea mai scurtă cale. Sau este o cale mai scurtă decât aceasta, așa că aceasta nu poate fi cea mai scurtă cale. Deci, acea transformare, cu siguranță, ar face ca toate ponderile să fie nenegative, dar nu ar păstra cele mai scurte căi. În special, dacă am adăugat aceeași greutate de margine la fiecare margine, voi orienta spre a lua căi care au mai puține margini, nu doar o greutate mai mică. Deci prima idee nu funcționează. Idee-- adăugați un număr mare la fiecare margine. Asta e rău. Face ca ponderile să nu fie negative, dar nu păstrează cele mai scurte căi. Deci aceasta nu este o idee bună, idee proastă. Există vreo modalitate prin care vă puteți gândi să modificați greutățile marginilor într-un grafic într-un fel care să păstreze cele mai scurte căi? Așadar, iată o idee pentru tine, care este un fel de acest pas critic în Johnson și într-o mulțime de algoritmi de transformare a graficului. Dacă am un vârf, spune tipul ăsta din mijloc, spune v, fiecare cale de la v trece printr-o margine de ieșire a lui v. Și fiecare cale care merge în v trece printr-o muchie care intră în v. Nu am spus nimic ... am spus lucruri foarte stupide. Dar această observație este critică aici. Dacă adaug un număr-- sau lasă-mă să văd dacă am înțeles corect în ceea ce privește adunarea și scăderea. Dacă adaug un număr la toate muchiile de ieșire dintr-un vârf și scad același număr din greutățile tuturor muchiilor de intrare la acel vârf, atunci fiecare cale de la v este schimbată cu aceeași cantitate, deoarece fiecare cale de la v merge printr-una din acele margini de ieșire. Și orice cale care merge în v s-a schimbat, de asemenea, cu aceeași cantitate. În special, este schimbat printr-un negativ, orice am adăugat la marginile de ieșire. Deci, o astfel de transformare, adăugând un număr din toate muchiile de ieșire dintr-un vârf și scăzând același număr din toate muchiile de intrare, păstrează cele mai scurte căi. Asta e o revendicare. Idee... aceasta este o idee mai bună. Având în vedere vârful v, adăugați... Voi pune asta pe două linii. Adăugați greutatea h la toate muchiile de ieșire și scădeți greutatea la toate muchiile de intrare. Deci asta e ideea. Și pretenția este că această transformare, cele mai scurte căi sunt păstrate sub această transformare. De ce, mă rog? Este cam același argument pe care l-am avut eu acolo. Dovadă - luați în considerare orice cale din graficul meu, fie dacă calea - calea ar putea trece prin v de multe ori, fie nu ar putea trece deloc. Dacă calea mea, dacă am o cale, în graficul meu original G, atunci cu greutatea drumului w de pi - aceasta este calea mea - trece prin v de un număr de ori. Așa că o să spun că asta merge de la s la t. Dacă traversează v-- dacă nu traversează niciodată v, dacă nu atinge niciodată v, vârful pe care l-am transformat, atunci susțin că greutatea traseului este aceeași pentru că nu am făcut nimic muchiilor care sunt pe această cale. Alternativ, chestia asta trece prin v uneori. Dacă trece prin v la mijloc, cum se schimbă greutatea căii mele? Ei bine, nu a făcut-o, pentru că am adăugat un număr la toate marginile de ieșire, așa că există un avantaj de ieșire aici cu greutatea pe care am schimbat-o în funcție de greutatea h. Și există un avantaj aici pe care l-am schimbat prin greutatea negativă h. Deci, acestea se anulează și ai 0. Deci trecerea printr- un vârf nu schimbă greutatea căii mele. Singurul mod în care aș putea schimba greutatea căii mele este dacă v este vârful de început sau vârful de sfârșit. Deci, este posibil ca s să fie vârful meu sau t să fie vârful meu. Ei bine, pentru orice cale care părăsește v, voi fi mărit greutatea acelei căi cu h, deoarece am adăugat o greutate h la toate muchiile de ieșire. Deci, din nou, în timp ce greutatea căii s-a schimbat, deoarece toate căile care părăsesc v s- au schimbat cu aceeași cantitate, o cale cea mai scurtă va fi totuși cea mai scurtă cale. Și același lucru este valabil și pentru t. Dacă t, vârful final este v, voi scădea h din toate muchiile mele de intrare, ceea ce înseamnă că orice cale care se termină la t, orice cale direcționată care se termină la t, se schimbă de asemenea cu aceeași valoare. Și așa că cele mai scurte căi trebuie păstrate. Deci cele mai scurte căi păstrate. Deci este o transformare destul de grozavă. Pot atribui oricărui vârf o astfel de transformare care afectează toate marginile care îl înconjoară prin acest factor aditiv h, fie adăugat, fie scăzut. Deci poate... și pot face asta independent pentru fiecare vârf. Cele mai scurte căi au fost păstrate de mine făcând asta la un vârf. Apoi, dacă o fac la un alt vârf, atunci cele mai scurte căi sunt încă păstrate. Și hai să dovedim asta foarte repede. Ceea ce voi face este că voi dori să fac acest lucru pentru a- mi oferi flexibilitate pentru a schimba toate greutățile muchiilor din graficul meu pentru a avea această proprietate. Voi stabili sau defini o funcție potențială h care mapează vârfurile la numere întregi. Deci, acesta este potențialul h al lui v. Și apoi vom face un grafic, G prim pe baza transformării de mai sus pentru fiecare vârf din v. Deci voi seta un număr, un h pentru fiecare vârf. Acestea sunt independente acum. Și voi adăuga acel potențial la toate marginile de ieșire. Și voi scădea acel potențial din toate marginile de intrare. Această transformare va păstra cele mai scurte căi. Să fim de fapt un pic mai riguroși decât așa este cazul când facem asta de mai multe ori. Așa că pretinde-- căile cele mai scurte sunt încă păstrate. Bine, ei bine, asta, din nou, nu este atât de greu de văzut. Să considerăm o cale de la s la t. Trece printr-o grămadă de vârfuri. O să le etichetez ca de la v0 la vk, astfel încât să le pot numerota. În regulă, acesta este v1 aici. Aceasta este o cale direcționată, v1, 2, 3, 4, până la k. Există k muchii în acest grafic. Vă pretind că orice cale de la v0 la vk, orice cale mai scurtă de la v0 la vk rămâne cea mai scurtă cale după ce reponderez totul în acest fel. Deci, să presupunem că aceasta este calea pi, și deci are greutatea w pi, care este de fapt doar suma tuturor greutăților marginilor de la vi minus 1 la vi, pentru că i este egal cu 1 la k. Aceasta este o notație slabă. Aceasta este greutatea muchiei de la vi minus 1 la i. Și avem -- se indexează de la 1 -- aceasta este prima muchie -- până la k, care este ultima muchie. Deci asta e greutatea drumului meu. Greutatea căii mele transformate... O voi face aici jos. Este un pic nedumerit. Greutatea traseului meu transformat pe care o voi spune este ponderea din acest nou grafic ponderat G prim. Această greutate a aceleiași căi -- este aceeași cale -- va fi doar suma tuturor muchiilor reponderate. Deci i este egal cu 1 la k din greutatea mea originală a muchiei mele, deci de la 0, i minus 1 la vi. Dar ce am făcut? Această margine este de ieșire de la vi minus 1. Deci este de ieșire, așa că adaug acea greutate-- acel potențial, îmi pare rău. Dar acea margine intră și în vi. Deci, când am reponderat lucrul, am obținut o scădere a lui h, vi. Acum, ce se întâmplă aici în suma, acest termen, dacă doar am luat suma peste acest termen, aceasta este exact calea mea inițială. Deci e bine. Dar veți observa că această sumă are k termeni, iar această sumă are scăderea a k alți termeni. Dar majoritatea acestor termeni sunt egali. De-a lungul traseului, toate marginile de intrare și de ieșire se anulează. Așa că ne rămâne doar să adăugăm potențialul la vârful de început și să scădem potențialul de la vârful final. Deci avem, adăugați h, v0 minus h, vk. Și de ce este bine? Ei bine, asta e bine pentru că fiecare cale de la v0 la vk începe la v0 și se termină la vk. Doar că... așa este. Așa am definit căile care merg de la v0 la vk. Dar fiecare astfel de cale, transformăm greutatea acelei căi adăugând o constantă asociată cu începutul și adăugând această valoare asociată cu sfârșitul. Și astfel, fiecare cale care merge de la v0 la vk se schimbă cu aceeași cantitate. Și așadar, dacă această cale pi a fost cea mai scurtă, este încă cea mai scurtă în graficul reponderat, deoarece tocmai am schimbat toate căile dintre cele două vârfuri cu aceeași cantitate. Acesta este un fel ca un argument telescopic aici în acest tip de dovezi. Dreapta. Deci avem, greutatea se schimbă. S-ar putea schimba, dar schimbă toate căile dintre aceste două vârfuri cu aceeași cantitate, ceea ce înseamnă că cele mai scurte căi sunt încă cele mai scurte. Minunat. OK, deci numele jocului este acum, avem acest instrument foarte flexibil. Avem acest instrument în care putem adăuga sau scădea greutatea din diferite margini. Dar trebuie să facem acest lucru într-un fel de mod localizat, restrâns. Trebuie să facem același lucru în jurul fiecărui vârf. Dar pare o tehnică de transformare puternică, poate că putem obține acest lucru pe care îl dorim, care este un prim G, o reponderare a graficului în care toate ponderile marginilor sunt pozitive sau nenegative. Deci, există un h astfel încât ponderile să fie toate pozitive? Ce înseamnă asta? w prim u, v, ponderea din noul meu grafic, în G prim, vreau ca aceste ponderi modificate, această pondere modificată a graficului meu, vreau ca fiecare dintre acestea să fie nenegativă. Deci există așa ceva? Huh. Ei bine, dacă rearanjez puțin această ecuație, această parte, obțin ceva care arată așa. h din v trebuie să fie mai mică sau egală cu h din u, plus greutatea unei margini de la u la v. Cum arată? Asta arată aproape exact definiția inegalității triunghiului. Cea mai scurtă cale de la un vârf de aici și cea mai scurtă distanță de cale de la același vârf aici, aceasta este doar o declarație a inegalității triunghiului. Deci, dacă putem seta aceste h să fie cea mai scurtă distanță de cale de la un vârf și acele distanțe cele mai scurte de cale sunt finite și nu minus infinit, atunci acest lucru se va menține prin inegalitatea triunghiului. Și în special, dacă ar fi să reponderăm muchiile pe baza acelor valori ale lui h, atunci obținem noi rate de margine care nu sunt negative. Minunat. BINE. Dar s-ar putea să nu existe vreun vârf de la care să putem accesa, la care să putem ajunge la toate vârfurile din grafic. În special, graficul meu ar putea să nu fie conectat. Dacă vreau această proprietate, am nevoie de toate acestea... Nu obțin nicio informație dacă aceste lucruri sunt infinite. Este complet adevărat. Infinitul este... nici măcar nu știu cum să compar infinitul și infinitul plus o constantă. Nu știu. Deci am nevoie ca toate aceste lucruri să fie finite. Deci, cum pot face aceste lucruri finite? Deci iată următoarea idee. Adăugați noul vârf s cu muchie 0-greutate la fiecare vârf, V în V. Luăm graficul nostru original. Adăugăm un nou supernod sau nod auxiliar s, cu o muchie 0-greutate la fiecare vârf din graficul meu. Cum arată asta? Acesta este ca... acolo este graficul meu original, iar acum am acest vârf s. Dar are margini direcționate în toate nodurile cu greutate 0. Asta e poza noastră. Și acest lucru nou îl voi numi, poate, graficul meu acum. Și afirmația este, ei bine, acum, dacă rulez un algoritm de calea cea mai scurtă , algoritmul de calea cea mai scurtă cu o singură sursă de data aceasta, de la s pentru a calcula cea mai scurtă distanță de cale la toate nodurile, cea mai scurtă distanță până la fiecare dintre vârfuri nu poate fi pozitiv, deoarece există un avantaj de 0-greutate. Deci, o cale de greutate minimă nu va fi mai mare de 0. Dacă este finită, atunci există o cale mai scurtă de lungime finită. Dacă este minus infinit, atunci există un ciclu negativ al ratei în graficul meu și mă pot opri. Deci sunt fie două situații. Dacă delta s,v este egal cu minus infinitul -- deci cred că acesta este, rulați cele mai scurte căi de la s. Și într-adevăr, deoarece acest grafic ar putea conține greutăți de margine negativă și ar putea conține cicluri negative, nu putem face mai bine decât să rulăm Bellman-Ford aici de la s pentru a calcula aceste căi. Dacă există în acest nou grafic acest G, dacă există un vârf care are pondere infinită negativă în graficul reponderat-- îmi pare rău, în graficul original G-- G nu a fost încă reponderat. Dacă există o distanță de greutate negativă de la s, atunci a existat un ciclu de greutate negativ în graficul original. De ce este asta? Ei bine, dacă acesta a fost setat la minus infinit, atunci există un ciclu de greutate negativ în grafic. Îngrijorarea este că acel ciclu de greutate negativă a fost adăugat la graficul meu prin adăugarea acestui vârf s. Dar ce știu despre vârful s? Nu are margini de intrare. Deci, niciun ciclu de greutate negativ nu ar putea trece prin s. Deci, orice ciclu de greutate negativă a fost în graficul original și pot avorta. Avorta. Yay. Altfel, ce fac? Ei bine, știu că cele mai scurte distanțe de drum aici ar satisface inegalitatea triunghiului. Deci, dacă reponderez cu h din v egal cu delta s din v, dacă setăm potențialele noastre în graficul nostru reponderat să fie cea mai scurtă distanță de cale de la supernodul nostru s, aceasta satisface inegalitatea triunghiului. Și pentru că nu există cicluri negative, toate aceste valori sunt finite. Și apoi această reponderare va duce la un grafic cu strict-- sau nu strict-- strict fără ponderi negative sau ponderi nenegative. Bine, minunat. Deci asta e practic. Aceasta este ideea din spatele algoritmului lui Johnson. Este într-adevăr o problemă de reducere sau un algoritm de reducere. Reducem de la rezolvarea unor tipuri de cele mai scurte căi cu semne, toate perechile, grafice în care ponderile lor ar putea fi pozitive sau negative și ne reducem la crearea unui grafic care are aceleași proprietăți ale căilor cele mai scurte , dar are doar greutăți de margine nenegative. Deci ne reducem de la un context semnat la un context de pondere non-negativ . Deci, algoritmul lui Johnson, care sunt pașii? Construiți G-uri din G, la fel ca aici sus. Fac un nou vârf s. Am pus o muchie direcționată cu greutate 0 de la s la fiecare vârf. Deci acesta este primul pas. Al doilea pas -- calculează E, s, v pentru toate V în V, adică -- sau de exemplu -- Bănuiesc că ar trebui să fie, adică pentru că nu prea am altă opțiune aici -- ci de Bellman-Ford. Aceasta este doar o singură cursă de Bellman-Ford aici. Calcula. Și apoi există două posibilități. Dacă există un delta s, v care este minus infinit, atunci anulați. Altfel, faceți-- sau reponderați graficul conform acestei scheme de reponderare, reponderând fiecare muchie din graficul meu original pentru a avea pondere-- noua noastră greutate, care este vechea noastră pondere, plus transformarea noastră. Acum, transformarea noastră va stabili acum h, v la acest delta s, v. Deci voi adăuga delta s, u și voi scădea delta s, v. Aceasta este schema noastră de reponderare. Doar identific h, v cu această distanță de cale cea mai scurtă aici. Și după ce am reponderat asta, pot rezolva cele mai scurte căi ale tuturor perechilor pe G prim cu Dijkstra. Și apoi calculați G distanțe de calea cea mai scurtă de la distanța de calea cea mai scurtă G prim . Calculați aceste distanțe față de celălalt folosind acest algoritm de aici -- puteți calcula distanțe în G de la distanțe în G prim în timp liniar-- sau îmi pare rău, de v ori timp liniar, timp liniar pentru fiecare s-- pentru fiecare vârf din graficul meu. OK, deci acesta este algoritmul. Practic, corectitudinea este banală. Am demonstrat deja-- întreaga parte a acestei prelegeri, partea interesantă a acestei prelegeri a dovedit că, dacă am avea o transformare bazată pe o funcție potențială care a schimbat muchiile de ieșire într-un mod simetric opus ca muchiile de intrare, atunci aceasta păstrează cele mai scurte căi . Și apoi realizând că inegalitatea triunghiului impune această condiție conform căreia ponderile marginilor vor fi nenegative în cadrul acestei reponderări, așa că găsim cele mai scurte distanțe de cale de la un alt vârf arbitrar și setăm funcțiile noastre potențiale să fie acele greutăți ale distanței pe calea cea mai scurtă . Facem reponderarea, pentru că acea reponderare păstrează cele mai scurte căi, ceea ce am argumentat deja. Atunci putem face... atunci aceasta are ponderi pe marginea pozitivă, așa că se aplică Dijkstra. Și apoi calcularea acestui lucru necesită o perioadă mică de timp. OK, care este timpul de rulare al acestui algoritm? Deci această parte, reconstruirea acestui lucru, aceasta necesită timp liniar. Eu doar adaug. Fac doar un nou grafic de aceeași dimensiune, cu excepția că am adăugat muchii v și un vârf. Computing-- fac Bellman-Ford pe acest nou grafic modificat, asta e doar-- O fac o dată. Asta durează de V ori E timp. Făcând această verificare, este nevoie doar de... Îmi fac bucla peste vârfurile mele. Asta necesită doar V timp. În caz contrar, făcând această reponderare, schimb greutatea fiecărei margini. Asta necesită timp de ordine E. Și apoi rezolvarea G prim -- rezolvarea celor mai scurte căi ale tuturor perechilor pe graficul de greutate a muchiei modificate cu Dijkstra durează de V ori Dijkstra. Asta e... Aș putea folosi un pic mai mult spațiu aici. Este de V ori V log, V plus E timp, care este de fapt timpul de rulare pe care îl căutăm. Am vrut să mă reduc la a nu folosi mai mult de această dată. Am folosit această perioadă de timp. Să ne asigurăm că încă nu am folosit nici mai mult. După aceea, calculăm aceste căi, așa cum sa demonstrat anterior, în V ori V plus E, care este mai mic decât atât. Și astfel, însumând toți acești timpi de rulare, acesta domină. Și astfel Johnson’s poate rezolva cele mai scurte căi ponderate cu semne ale tuturor perechilor, cele mai scurte căi semnate ale tuturor perechilor, nu în V ori Bellman-Ford, așa cum am avut înainte aici, dar mai rapid, în aproape liniar pentru grafice rare, doar fără acest factor log . Deci am avut o îmbunătățire destul de mare. Deci, lucrul bun despre cele mai scurte căi ale tuturor perechilor este că, într-adevăr, nu trebuie să suportăm acest cost mare în contextul ponderilor negative. În esență, rulăm Bellman-Ford o dată pentru a vedea dacă există un ciclu de greutate negativ în graficul meu. Dacă este, economisesc multă muncă oprindu-mă mai devreme. Deci ăsta e al lui Johnson. Acesta este sfârșitul prelegerilor noastre despre grafice. Vom avea o sesiune de revizuire și de probleme despre cum să rezolvăm problemele, grafic probleme folosind acest material. Dar am vorbit despre o mulțime de lucruri diferite până acum. Am vorbit despre accesibilitatea graficului, componentele conectate, detectarea ciclurilor, detectarea ordinelor de sortare topologice ale unui DAG. Am vorbit despre găsirea de cicluri de greutate negative, algoritmi de calea cea mai scurtă cu o singură sursă și acum, în sfârșit, astăzi, algoritmi de calea cea mai scurtă cu toate perechile , cu un algoritm nou care nu este într-adevăr un algoritm cu totul nou. Nu a trebuit să facem nicio dovadă prin inducție aici. Într-adevăr, munca grea care se întâmplă este că ne reducem la utilizarea fie Dijkstra, fie Bellman-Ford pentru a face greutățile de a găsi eficient căile cele mai scurte de la o singură sursă . Așadar, Johnson este doar un lipici pentru a transforma un grafic într-un mod inteligent și apoi se reduce la utilizarea mai rapidă a unora dintre algoritmii cu cele mai scurte căi . Deci aceasta este unitatea noastră de grafice. Următoarea noastră prelegere, vom începe să vorbim despre o formă generală a, nu vă prezentând un algoritm, ci cum să vă proiectați propriul algoritm în contextul programării dinamice. Deci ne vedem următoarea prelegere.