Ecotehnica Cultivarii Tutunului si Hameiului
TIPUL DE SOL DIN REGIUNEA BUCURESTI Soluri de tip hidromorf si brun-roscate Caracteristici :...
Acest curs prezinta Grafuri. Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).
Arhiva contine 8 fisiere pdf de 507 de pagini (in total).
Profesor: Șl. Dr. Ing. Șerban Radu
Iti recomandam sa te uiti bine pe extras si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.
Fratele cel mare te iubeste, acest download este gratuit. Yupyy!
Domeniu: Agronomie
Problema drumului de lungime minimă din orice vârf
-
Problema se referă la aflarea costului minim din orice vârf către oricare alt vârf, folosind muchii multiple
-
Aceasta se numește problema drumului de lungime minimă din orice vârf (all-pairs shortest path problem)
Algoritmul lui Floyd
-
Algoritmul lui Warshall reprezintă o modalitate rapidă de a crea un tabel care indică vârfurile în care se poate ajunge dintr-un anumit vârf, într-unul sau mai mulți pași
-
O abordare similară pentru grafuri ponderate este folosită de algoritmul lui Floyd, descoperit de Robert Floyd în 1962
Observații
-
Matricea de adiacență indică costurile tuturor căilor cu o singură muchie
-
Se dorește extinderea acestei matrici pentru a indica costurile tuturor căilor, indiferent de lungimea lor
-
De exemplu, se poate ajunge de la B la C cu un cost de 30 (10 de la B la D și 20 de la D la C)
Observații
-
Similar algoritmului lui Warshall, se modifică matricea de adiacență
-
Se examinează fiecare celulă de pe fiecare rând
-
Dacă există o pondere pozitivă, de exemplu 30 la intersecția liniei C cu coloana A, atunci se analizează coloana C, deoarece C reprezintă linia unde se află 30
Observații
-
Dacă se găsește o celulă în coloana C, de exemplu 40 la linia D, atunci există o cale de la C la A cu o pondere de 30 și o cale de la D la C cu o pondere de 40
-
Se poate deduce că există o cale cu două muchii de la D la A, cu o pondere de 70
Observații
-
Linia A este vidă
-
Pe linia B este 70 în coloana A și 10 în coloana D, dar coloana B este vidă, deci muchiile care încep din B nu pot fi combinate cu nicio muchie care se termină în B
Observații
-
În linia C se află 30 pe coloana A
-
În coloana C se află 20 pe linia D
-
Muchia de la C la A are o pondere de 30
-
Muchia de la D la C are o pondere de 20
-
Se obține calea de la D la A cu ponderea de 50
Observații
-
Linia D arată o situație interesantă - se poate micșora un cost existent deja
-
Pe linia D există 50 în coloana A
-
Pe linia B există 10 în coloana D
-
Există o cale de la B la A cu costul 60
-
Cu toate acestea, există deja costul 70 pe linia B, în coloana A
Observații
-
Deoarece 60 e mai mic decât 70, se înlocuiește 70 cu 60
-
În cazul căilor multiple de la un vârf la altul, tabelul indică calea de cost minim
Observații
-
Implementarea algoritmului lui Floyd este similară algoritmului lui Warshall
-
În locul inserării valorii 1 în tabel, cum se procedează în algoritmul lui Warshall, când se găsește o cale cu două muchii, se adaugă costul căii cu două muchii și se inserează suma costurilor celor două muchii în tabel