Porniți algoritmul de dextrare de la punctul de pornire. Este posibil pentru O (N2). este posibil pentru O (Mlog (n)). Pentru a verifica existența, mai întâi umplem matricea de distanță cu o anumită constantă constantă = INF.
Distanța dintre vârfuri
Aici, va trebui să scrieți cu sinceritate un dejkstra cu o grămadă sau set. De asemenea, vom seta matricea strămoșilor pentru a restaura calea părintelui [v]. în care va fi stocat strămoșul vertexului v, de unde am ajuns la acest vârf. Actualizăm parintele [v] în două cazuri, când a venit prima oară la v sau a obținut o distanță mai mică decât distanța [v]. Dacă calea există, putem restaura calea cu ajutorul matricei strămoșilor pornind de la vârful final, urcând strămoșii până ajungem la punctul de plecare. De asemenea, merită remarcat faptul că aici este necesar să se scrie algoritmul dextra pe listele de contiguitate.
Rulați algoritmul Ford-Bellman. Verificarea neresistenței căii se face standard - dacă după n iterații dist [u] = INF (pe care ați specificat-o inițial), atunci nu există nici o cale de la s la u. Rețineți că o cale infinită de scurtă poate fi numai în cazul unui ciclu de greutate negativ, dar asta nu este tot. Pe lângă faptul că trebuie să existe un astfel de ciclu, acesta trebuie să fie încă accesibil de la punctul de pornire, iar punctul final trebuie să fie accesibil din acest ciclu. Cu ajutorul lui Ford-Bellman găsim un vârf din fiecare ciclu. De exemplu, hai să creăm două rânduri booleene [] și pathrev []. unde calea [v] = adevărată. dacă putem ajunge la v de la punctul de plecare. pathrev [v] = adevărat. dacă putem obține de la vârful v la vertex u. Prima matrice este completă prin căutarea în profunzime a graficului sursă, iar pathrev [] pe cea transpusă. Acum, dacă există un vertex v. care aparține unui anumit ciclu negativ și este adevărat și pentru acea cale [v] · pathrev [v] = adevărată. atunci răspunsul este "-", în caz contrar distanța descoperită de algoritmul Ford-Bellman.
Algoritmul standard al lui Floyd, analizat la conferința de ieri.
O problemă similară este problema „calea cea mai scurtă“, dar aici trebuie să faceți truc, pentru că trebuie să găsim nu este cea mai scurtă și cea mai lungă cale, trebuie să modificați greutățile de marginile pe opuse - se înmulțește cu -1.
Standard bfs pe un singur grafic, nimic special, analizat la conferința de ieri.
Cea mai scurtă cale a unui cal Să ne imaginăm celulele de șah ca vârfurile unui grafic. Două vârfuri ale lui A. B vor fi conectate între ele dacă calul se poate deplasa de la A la B. Fiecare margine va avea o greutate unitară. Rămâne să rulați căutarea în lățime și apoi să restaurați calea.
Cea mai scurtă cale a doi cai
Graficul este același ca în cazul problemei precedente. Acum, în linie (vector) va stoca nu numai coordonatele un cal, și o dată coordonatele doi cai, plus tot ceea ce avem nevoie să ne amintim ce a caii face în prezent următoarea mișcare. Introduceți inițial coordonatele de pornire ale celor doi cai, precum și un pavilion corespunzător faptului că primul cal (după condiție) se plimba. Vom folosi matricea [], unde [x1] [y1] [x2] [y2] = true. dacă anterior exista o poziție de doi cai, în care primul cal se află în (x1; y1). și al doilea în (x2; y2). Următorul pas de a căuta în lățime va fi următoarea: suntem în coada de așteptare (vectorul) Am ajunge la următoarea pereche de coordonate, dacă este utilizat într-o anumită condiție este adevărată, cazurile continuă, în caz contrar se uite la ceea ce unii dintre caii sunt acum de mers pe jos în jurul și încearcă să meargă la starea corespunzătoare, adică presupunem că caii pe rând - au luat o pereche de coordonate, sa uitat la ea, și a cărui rândul său este de a schimba coordonatele calului, dacă sunt utilizate de noua stare de fals, apoi a pus în aplicare). Dacă într-un anumit moment am descoperit că coordonatele ambilor cai coincid cu destinația lor finală, vom termina bfs și vom restabili strămoșii.
Notă: în această sarcină este mai bine pentru a stoca statul nu este în coada de așteptare, și vectorul și, în loc în timp ce faci pe acest simplu vector pentru, deoarece vectorul este mai convenabil pentru a restabili strămoșii, tot ce va fi nevoie pentru a restabili strămoșii în cazul vectorului este în fiecare stat stocați, de asemenea, indicele stării-mamă în vector.
Nu a alerga doar BFS nu funcționează, așa cum vom prezenta margini, care au o greutate de la 0, 1, 2. Cum se solicită cel mai scurt traseu, în cazul graficului 0-1, am discutat la curs, dar ce să facă cu greutatea înotătoarelor 2. Răspunsul este simplu - pentru a rupe partea superioară în două. De exemplu, avem două noduri a și b. a căror greutate este egală cu două. Vom face un vertex fictiv c. și înlocuiți muchia (a. b) greutatea două câte două nervuri (a. c) și (c. b) greutate una, deoarece greutatea nervura pentru kadogo 2. Ca rezultat, obținem graficul, ale cărei muchii au o greutate de 0 sau 1 și Cea mai scurtă cale pentru o astfel de problemă o putem găsi deja prin bfs. Merită să ne amintim când vom reface calea, despre înlocuirea noastră și nu vom lua vârfuri fictive.
Distanta de radacina
Această sarcină este ultima în ordine, dar, evident, nu cea mai dificilă, bine făcută pe cei care au avut suficientă forță pentru a termina termenii tuturor sarcinilor până la sfârșit. Soluția este simplă - puteți executa bfs, Ford Bellman, Dijkstra, Floyd sau chiar df-uri regulate, deoarece problema este dată unui copac. Apoi găsiți distanța față de toate vârfurile de la punctul de pornire, pentru dfs distanța este aceeași cu înălțimea vârfului arborelui.