Unelte utilizator

Unelte site


laboratoare:laborator-07

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

Both sides previous revision Versiuni anterioare
laboratoare:laborator-07 [2017/04/07 13:55]
iulian.matesica [6. Exercițîi laborator]
laboratoare:laborator-07 [2018/02/25 20:45] (curent)
mihai.iacov
Linia 1: Linia 1:
-====== Laborator 07: Drumuri ​de cost minim ======+====== Laborator 07: Arbori minimi ​de acoperire ​======
  
-===== 1.Obiective laborator ​====== +===== 1. Obiective laborator===== 
-  * Înțelegerea ​ideii de cost și de drum minim într-un graf +  * Înțelegerea ​conceptului ​de arbore minim de acoperire ​ 
-  * Prezentarea ​algoritmilor care calculează drumul de cost minim +  * Înțelegerea implementării ​algoritmilor care determină acest arbore 
-  * Înțelegerea ​aplicațiilor practice ​prezente ​în: +  * Înțelegere ​aplicațiilor practice în: 
-    * găsirea drumului minim între 2 locații (ex: GPS+    * rețele de calculatoare:​ obținerea unui cost redus la interconectarea mai multor stații (ex: protocolul STP folosit în LAN-uri
-    * rutarea în cazul rețelelor ​de calculatoare ​(ex: protocolul RIP)+    * prelucrarea ​de imagine: segmentarea cadrelor ​(ex: folosită în analiza medicală) 
 +    * în clustere: determinarea unei topologii de comunicare, în cazul în care topologia nu era una regulată(arbore,​ inel)
  
-{{ :​laboratoare:​rip.gif?600 | RIP protocol}} +{{ :​laboratoare:​segmentation.jpg?600 | Segmentarea de imagini}}
-===== 2.Considerente teoretice ======+
  
 +===== 2. Introducere =====
  
-==== 2.1 Costul unei muchii ​==== +==== 2.1 Conexitate în grafuri ​====
-La fel ca la arbori de acoperire, presupunem că fiecare muchie are un **cost de parcurgere**.+
  
-==== 2.2 Costul unui drum; drumul de cost minim ==== +===Componentă conexă=== 
-Într-un ​graf, orice drum este definit de o succesiune de muchii (cu proprietatea că, pentru ​oricare două muchii consecutive ​din succesiune, nodul destinaţie/de sosire al primei muchii ​este acelaşi ​cu nodul sursa/de plecare al celei de-a doua muchii).+O componentă conexă a unui graf **neorientat** ​este un subgraf ​cu următoarele proprietăţi:​ 
 +  - oricare două noduri ​din acest subgraf sunt **conectate**(există un lanţ între ele) 
 +  - orice nod din acest subgraf **NU este conectat** ​cu niciun nod din afara subgrafului(nodurile din componentă fac muchii ​numai cu alte noduri din componentă)
  
-Costul unui drum va fi definit ca **suma costurilor** muchiilor ce compun acel drum.+<note important>​Orice graf neorientat are cel puţin o componentă conexă.</​note>​
  
-Fie un nod sursă(S) şi un nod destinaţie(D). Pot exista mai multe drumuri de la S la D(drumuri care au S primul nod, D ultimul nod), iar drumul de cost minim de la S la D va fi cel mai ieftin(cu costul cel mai mic) dintre acestea.+===Graf neorientat conex=== 
 +Un graf neorientat este numit **conex** dacă are o singură **componentă conexă**.
  
-<​note ​important>Pot exista mai multe drumuri de cost minim de la S la D.</​note>​+<​note ​tip>Putem explora toate nodurile dintr-un graf neorientat conex dintr-o singură parcurgere a grafului(DFS sau BFS).</​note>​
  
-====2.3 Legătura muchii-arce:​ ==== +===Graf orientat slab conex=== 
-<note tip> +Fie graful neorientat asociat unui graf orientat obţinut prin înlocuirea tuturor ​**arcelor** cu **muchii**. Atunci un graf orientat este **slab conex** dacă graful neorientat asociat acestuia este conex.
-Orice graf **neorientat** este echivalent ​cu un graf **orientat** dacă înlocuim fiecare ​**muchie** cu **două arce**(de acelaşi cost, câte un arc pentru fiecare sens).+
  
-Algoritmii următori pot fi folosiţi(în limita observaţiilor finale) pe grafuri orientate la fel ca pe grafuri neorientate. +===Graf orientat tare conex=== 
-</​note>​+Un graf orientat este **tare conex** dacă există drum între oricare două noduri, atât într-un sens, cât şi în celelalt.
  
 +Se pot defini similar componentele slab conexă şi tare conexă.
  
-===== 3.Drumul de cost minim cu sursă unică ====== +==== 2.2 Arborele văzut ca graf ==== 
-Următorii algoritmi caută drumurile de cost minim de la **un singur nod(sursă)** la **toate celelalte noduri**. Rezultatul acestor algoritmi este un **arbore ​cu drumuri ​de cost minim**, unde: +Folosind noţiunile de mai sus, putem spune că un arbore este un graf(pentru simplitate, fie neorientat) **conex** şi cu număr minim de muchii, prin urmare, **aciclic**. 
-  ​nodul sursă(S) este rădăcina arborelui;​ +==== 2.3 Arbore vs. pădure de acoperire ==== 
-  ​* toate nodurile ​din graf sunt în arbore; +Pentru ​un graf neorientat, construirea unui arbore ​de acoperire(nu neapărat ​de cost minim) presupune construirea unui arbore care să fie **graf parţial**(să **acopere** toate nodurile).
-  * pentru orice nod destinaţie(D), costul drumului din arbore de la rădăcina S la D este drum de cost minim(de la S la D) în graf.+
  
 +Acest lucru este posibil numai dacă graful este **conex**. În caz contrar, se poate construi câte un arbore de acoperire pentru fiecare **componentă conexă** a grafului, spunând că se construieşte o **pădure** de acoperire pentru graf.
  
-==== 3.1 Algoritmul lui Dijkstra ​====+==== 2.4 Arbore de cost minim ==== 
 +Dacă fiecare muchie dintr-un arbore are un **cost**(o pondere), atunci **costul arborelui** este dat de **suma costurilor** muchiilor ce formează arborele.
  
-Algoritmul lui Dijkstra se bazează pe un principiu similar cu cel al algoritmului lui Prim: +Dacăpe acelaşi principiufiecare muchie dintr-un graf are un cost, atunci alegerea unui **arbore minim de acoperire** presupune alegerea unui arbore care să acopere toate nodurile şi care să folosească muchiile ce dau suma costurilor minimă. 
-  * iniţial, toate nodurile sunt neexplorate ​şi vom construi arboreleîncepând de la nodul S; +===== 3Algoritmul lui Kruskal =====
-  * atribuim ​un posibil ​cost(o estimare a distanţei) pentru fiecare nod. (iniţialS are costul 0, toate celelalte noduri au costul ​**infinit**); +
-  * la fiecare pas, alegem cel mai bun candidat dintre nodurile neexplorate,​ urmând ​să îl explorăm(să îi evaluăm vecinii), iar acel candidat va rămâne în arbore; +
-  * la fiecare explorare(evaluare a vecinilor), dacă găsim o nouă estimare de cost mai bună decât cea precedentă,​ folosim, mai departe, noua estimare. Dacă dorim să ţinem evidenţa muchiilor folosite, actualizăm şi nodul părinte al vecinului respectiv.+
  
-Diferenţa apare, în algoritmul ​lui Dijkstra, la funcţia folosită pentru estimarea costurilor, atunci când evaluăm vecinii unui nod: +Algoritmul ​lui Kruskal ​este un algoritm în teoria grafurilor ​care găsește arborele parțial de cost minim pentru ​un graf conex ponderat
-  * Dacă C este nodul curent(pe ​care îl explorăm), atunci: +
-  * pentru ​fiecare nod vecin(V) al lui C, noul cost posibil va fi costul drumului S-V(de la S la V) care trece prin C, mai exact - suma dintre costul drumului S-C şi costul muchiei (C,V).+
  
-<note tip>​Construind astfel algoritmuleste **garantat** că, în momentul în care explorăun nod(C), estimarea pentru costul drumului S-C este chiar **costul minim**.</​note>​+Cu alte cuvintegăsește submulțimea muchiilor ​care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului
  
-<note important>​ +Dacă graful nu este conexatunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru ​fiecare componentă conexă). Algoritmul ​lui Kruskal este un exemplu ​de **algoritm greedy**.
-Pentru grafuri orientate, ne referim la vecinii la care putem ajunge printr-un arc ce pleacă din C: (C,V). +
-</​note>​ +
-Paşii algoritmului lui Dijkstra: +
-<​code>​ +
-1. Declarăm două mulţimi: +
- mulţimea nodurilor neexplorate(MN),​ iniţial MN conţine toate nodurile; +
- mulţimea nodurilor explorate(ME) ce compun arborele, iniţial ME = vidă; +
-2. Atribuim fiecărui nod o estimare iniţială a costului: +
-pentru ​nodul sursă(S); +
- infinit pentru toate celelalte;​ +
-3. Cât timp există noduri în MN +
- 1. Alegem, din MN(nodurile neexplorate), nodul cu cel mai mic cost estimat +
- îl numim C(nodul curent) +
- 2pentru fiecare din vecinii ​lui C care se află în MN  +
- 3. calculăm noua estimare ​de cost = cost(drumul S-C) + cost(muchia (C,V)); +
- 4comparăm noua estimare cu vechiul cost(drumul S-V): +
- dacă noul cost e mai bun +
- 1. actualizăm cost(drumul S-V) = noul cost; +
- 2. actualizăm parinte(V) = C; (pentru păstrarea muchiei folosite) +
- altfel păstrăm vechiul cost +
- 5. Marcăm nodul C ca explorat: îl eliminăm din MN şi îl adăugăm în ME. +
- (Nu va mai fi verificat) +
-</​code>​+
  
-==== 3.2 Algoritmul Bellman-Ford ==== +<note tip> 
-Principii similare pentru algoritmul Bellman-Ford:​ +Algoritmul funcționează în felul următor:
-  * vom construi arborele, începând de la nodul S; +
-  * atribuim un posibil cost(o estimare a distanţei) pentru fiecare nod. (iniţial, S are costul 0, toate celelalte noduri au costul **infinit**);​ +
-  * la fiecare evaluare, dacă găsim o nouă estimare de cost mai bună decât cea precedentă,​ folosim, mai departe, noua estimare. Dacă dorim să ţinem evidenţa muchiilor folosite, actualizăm şi nodul părinte. +
-  * funcţia de estimare a costului este definită la fel ca la algoritmul lui Dijkstra(costul drumului de la S la nodul respectiv) +
- +
-<note tip>Rezultatul algoritmului va fi un arbore cu N noduri(unde N = |V|, numărul de noduri din graf). Prin urmare, **lungimea** oricărui drum de la S la alt nod va fi **maxim N-1**. (Presupunem că nu se repetă muchii) +
-</​note>​+
  
-Diferenţa apare, în algoritmul Bellman-Ford,​ la alegerea nodurilor pentru care facem evaluarea:​ +  ​ ​creează o pădure F (o mulțime de arbori)unde fiecare ​vârf din graf este un arbore separat 
-  ​Algoritmul nu are preferinţe pentru anumite noduri şi nu extragela fiecare ​pas, cel mai bun candidat. +  *  ​creează o mulțime S care conține ​toate muchiile ​din graf 
-  * În schimb, acest algoritm evaluează **toate muchiile** ​la un pas. Folosindu-se ​de principiul de mai sus(N-1) astfel de paşi vor fi suficienţi.+  ​ atât timp cât S este nevidă 
 +      ​elimină o muchie ​de cost minim din S 
 +      * dacă acea muchie conectează doi arbori distincțiatunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur 
 +      * altfel, ignoră muchia
  
-<note important>​ 
-În cazul grafurilor neorientate,​ evaluăm fiecare muchie în ambele sensuri. 
 </​note>​ </​note>​
  
-Paşii algoritmului Bellman-Ford: +{{ :laboratoare:kruskal.gif?900 |}}
-<​code>​ +
-1. Atribuim fiecărui nod o estimare iniţială a costului: +
- 0 pentru nodul sursă(S);​ +
- infinit pentru toate celelalte;​ +
-2. Executăm de N-1 ori: +
- 1. Pentru fiecare pereche (u, v) a.i. există muchie de la u la v +
- 1. calculăm noua estimare de cost = cost(drumul S-u) + cost(muchia (u,v)); +
- 2. comparăm noua estimare cu vechiul cost(drumul S-v): +
- dacă noul cost e mai bun +
- 1. actualizăm cost(drumul S-v) = noul cost; +
- 2actualizăm parinte(v) = u; (pentru păstrarea muchiei folosite) +
- altfel păstrăm vechiul cost +
-</​code>​+
  
-===== 4.Drumul de cost minim între oricare 2 noduri ====== 
-Următorul algoritm caută cel mai scurt drum de la **orice nod sursă(S)** la **fiecare nod destinaţie(D)**. 
  
 +{{ :​laboratoare:​kruskal2.gif?​900 |}}
 +===== 4. Algoritmul lui Prim =====
  
-==== 4.1 Algoritmul ​Floyd-Warshall ==== +Algoritmul ​lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial ​de cost minim al unui graf conex ponderatÎnseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat
-Rezultatul algoritmului ​este o matrice N x N(unde N = |V|, numărul de noduri), iar valorea din matrice de la poziţia [i][j] va fi costul ​minim pentru drumul i-jFie această matrice numită **dist**.+
  
-Pentru simplitate, algoritmul numerotează nodurile de la 1 la N şi foloseşte următoarea construcţie:​ +<note tip> 
-  * defineşte o funcţie costMinim(i,j,k) = cel mai ieftin drum care: +Algoritmul incrementează mărimea unui arborepornind ​de la un nod, până când sunt incluse toate nodurile.
-  *    -pleacă din i +
-  *    -ajunge în j +
-  *    -în afară ​de primul şi de ultimul ​nod, conţine numai noduri din {1,​2,​3,​...,​k}(primele k noduri).+
  
-Algoritmul calculează costMinim(i,j,k) pentru toate perechile (i,j,k), folosind formula**costMin(i,​j,​k+1) ​min(costMin(i,j,k), costMin(i,k+1,k+ costMin(k+1,j,k))**; +    * Intrare: Un graf conex ponderat cu nodurile V șmuchiile E. 
- +    * InitializareVnou {x}unde x este un nod arbitrar ​(punct de plecaredin VEnou= {} repetă până când Vnou=V
-<note tip> +        Alege muchia ​(u,vdin E de cost minim astfel încât u este în Vnou șv nu e (dacă există ​mai multe astfel ​de muchii, se alege arbitrar) 
-Observaţii+        * Se adaugă v la Vnou, (u,vla Enou 
-  costMin(i,j,0= costMuchie(i,j) (dacă există ​muchie ​de la i la j) sau infinit(altfel); +    Ieșire: Vnou șEnou descriu arborele parțial ​de cost minim
-  costMin(i,j,N) = drumul ​de cost minim de la i la j.+
  
 </​note>​ </​note>​
  
-Paşii algoritmului Floyd-Warshall:+{{ :laboratoare:​prim.gif?​900 |}}
  
-<​code>​ 
-1. Declarăm matricile: 
- dist, matrice N x N şi o iniţializăm dist[i][j] = infinit, pentru orice i şi j 
- next, matrice N x N în care vom salva prima muchie din drumul i-j de cost minim 
- //next este necesar doar în cazul în care ne interesează muchiile folosite 
-//pasul k = 0 
-2. Pentru fiecare nod v 
- 1. dist[v][v] = 0; 
-3. Pentru fiecare pereche (u,v) a.i. există muchie de la u la v 
- 1. dist[u][v] = costMuchie(u,​v);​ 
- 2. next[u][v] = v; //pentru urmărirea muchiilor ce compun drumul 
-//am terminat pasul k = 0 
-4. Pentru fiecare pas k (de la 1 la N) 
- 1. Pentru fiecare nod i (de la 1 la N) 
- 1. Pentru fiecare nod j (de la 1 la N) 
- 1. calculăm costul nou = dist[i][k] + dist[k][j]; 
- 2. comparăm costul nou cu costul vechi = dist[i][j] 
- dacă e mai bun costul nou: 
- 1. dist[i][j] = costul nou; 
- 2. next[i][j] = next[i][k]; //pentru urmărirea muchiilor 
- altfel păstrăm costul vechi 
-</​code>​ 
  
-Pentru obţinerea nodurilor ce formează drumul de cost minim de la u la v, putem folosi următoarea secvenţă: 
-<​code>​ 
-funcţie afişareDrum(u,​ v) 
-1. dacă u == v 
- 1. print(v); STOP 
-2. print(u); 
-3. afişareDrum(next[u][v],​ v); 
-</​code>​ 
  
-===== 5. Observaţii finale ​=====+{{ :​laboratoare:​prim2.gif?​900 |}} 
-<note tip> +===== 5. Exerciții de laborator ​=====
-Cei 3 algoritmi funcţionează bine atunci când **toate muchiile** au **cost pozitiv**. +
-</​note>​ +
-<note warning>​ +
-Drumul de cost minim **NU** este bine definit atunci când există **cicluri cu cost negativ**. +
-  * putem ajunge de la un nod la acelaşi nod, folosind acelaşi ciclu de oricâte ori => costMinim = -infinit);​ +
-  * în aceste cazuri, nu putem pune problema găsirii drumurilor de cost minim. +
- +
-</​note>​ +
-<note warning>​ +
-O **muchie cu cost negativ** este echivalentă cu **2 arce cu cost negativ** şi implică existenţa unui ciclu cu cost negativ. +
-</​note>​ +
-<note tip> +
-Algoritmii **Bellman-Ford** şi **Floyd-Warshall** pot detecta dacă un graf conţine **cicluri cu cost negativ**:​ +
-  * Bellman-Ford:​ executăm încă o evaluare a tuturor muchiilor la final. Dacă găsim cel puţin o estimare nouă mai buna, graful conţine măcar un ciclu cu cost negativ. +
-  * Floyd-Warshall:​ putem verifica, la fiecare pas, dacă avem o valoare negativă pe diagonala matricei dist. Dacă găsim cel puţin o valoare negativă, graful conţine măcar un ciclu cu cost negativ. +
- +
-</​note>​ +
-<note important>​ +
-Pentru algoritmul lui **Dijkstra**,​ "​garanţia"​ se pierde când există chiar şi **un singur arc cu cost negativ**. +
-  * Algoritmul se bazează pe ideea că, odată explorat un nod, drumul de cost minim până la acel nod a fost găsit, ceea ce **NU** este mereu corect în prezenţa unui arc cu cost negativ. +
-  * De aceea, algoritmul poate produce răspunsuri **greşite** în acest caz. +
- +
-</​note>​ +
-<note tip>În schimb, algoritmii **Bellman-Ford** şi **Floyd-Warshall** funcţionează pe grafurile cu **arce cu cost negativ**, atâta timp cât drumurile de cost minim sunt bine definite(**fără cicluri cu cost negativ**). +
-</​note>​+
  
-===== 6Exerciții laborator ======+1.Vi s-a asignat rolul de nou coordonator al departamentul de rețelistică al companiei Coca Cola (Pepsi petru cei cărora nu le place Cola). Sediul companiei are arondate N-1 sucursale, iar voi trebuie să asigurațu conectivitate între toate locațiile folosind o lungime minimă de fibră optică, lucru care duce implicit la reducerea costurilor totale. ​
  
-  - Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite. +<file cpp> 
-  - Cum putem folosi algoritmul lui Dijkstra sau algoritmul Bellman-Ford pentru a obţine aceleaşi rezultate ca algoritmul Floyd-Warshall(drumul de cost minim pentru toate perechile de noduri)? Ne limităla grafurile pe care merg toţi cei trei algoritmi. +# explicatii format  
-  - Implementaţi ​unul din algoritmi ​pentru ​a calcula drumurile de cost minim de la un nod sursă la toate celelalte noduri într-un graf cu toate muchiile/​arcele cu cost pozitiv. +# n=numar varfuri ​m=numar muchii 
-  ​- Verificaţi dacă un graf conţine cicluri negative.+# m randuri, cate unul pentru ​fiecare muchie: start end cost 
 +8 13   
 +1 2 4  
 +1 3 9 
 +1 4 1 
 +1 6 7 
 +2 3 12 
 +2 4 4 
 +3 8 13 
 +4 5 7 
 +4 6 8 
 +5 6 3 
 +5 7 6 
 +5 8 5 
 +7 8 2 
 +</​file>​
  
-====6.1. Exerciții - schelet de laborator==== +====5.1. Exerciții - schelet de laborator==== 
-Pentru acest laborator puteți descărca scheletul de cod de [[http://​elf.cs.pub.ro/​sda-ab/​wiki/​_media/​laboratoare/​lab7_drumuri_minime-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. ​+Pentru acest laborator puteți descărca scheletul de cod de [[http://​elf.cs.pub.ro/​sda-ab/​wiki/​_media/​laboratoare/​lab6_arbori_min-skel.zip|aici]]. Descărcați arhiva și dezarhivați-o. ​
  
 === Linux=== === Linux===
 Puteti folosi utilitarul ''​%%wget%%''​ pentru descarcare si utilitarul ''​%%unzip%%''​ pentru dezarhivare. Puteti folosi utilitarul ''​%%wget%%''​ pentru descarcare si utilitarul ''​%%unzip%%''​ pentru dezarhivare.
  
-  * ''​%%wget http://​elf.cs.pub.ro/​sda-ab/​wiki/​_media/​laboratoare/​lab7_drumuri_minime-skel.zip%%''​ +  * ''​%%wget http://​elf.cs.pub.ro/​sda-ab/​wiki/​_media/​laboratoare/​lab6_arbori_min-skel.zip%%''​ 
-  * ''​%%unzip ​lab7_drumuri_minime-skel.zip%%''​+  * ''​%%unzip ​lab6_arbori_min-skel.zip%%''​
  
 Pentru compilare folositi comanda ''​%%make%%''​. Pentru rulare puteti folosi comanda ''​%%make run%%''​ sau ''​%%./​graph%%''​. Pentru compilare folositi comanda ''​%%make%%''​. Pentru rulare puteti folosi comanda ''​%%make run%%''​ sau ''​%%./​graph%%''​.
  
  
-===Extra=== +==== Extra ==== 
- +  - Se dă un graf care coincide cu un arbore ​minim de acoperire. Verificaţi dacă, introducând o nouă muchie în graf, costul ​arborelui minim de acoperire se schimbă şi, dacă da, găsiţi muchia ​ce va fi scoasă
-  - Se dă un graf pentru ​care se cunoaşte drumul de cost minim de la un nod sursă(S) la un nod destinaţie(D). Dacă adăugăm 100 la costul ​fiecărei muchiise modifică drumul de cost minim? (dacă da, daţi un exemplu; dacă nu, explicaţi de ce)+  - Se dă un graf care coincide cu un arbore minim de acoperire ​şi un vector(V) cu K noduri din graf. Care este costul minim al muchiilor pe care trebuie să le eliminaţi din graf pentru ca fiecare ​nod din vectorul V să se afle în altă componentă conexă. (Să nu existe drum între oricare două noduri din vectorul V)
-  - Aceeaşi întrebare dacă înmulţim fiecare ​cost cu 100+  - Se dă un graf care coincide ​cu un arbore ​minim de acoperire ​şi un nod auxiliar ​care formează doar două muchii. Verificaţi dacă folosirea ​nodului auxiliar ​pentru a conecta nodurile duce la un arbore ​de acoperire cu un cost mai mic.
-  - Cum găsiţi(mai rapid decât ​cu cei 3 algoritmi prezentaţi) drumul de cost minim de la S la D într-un graf în care toate muchiile au acelaşi cost(1)? Cum adaptaţi soluţia în cazul în care toate muchiile au costul 1 sau 2? +
-  - Daţi un exemplu în care folosirea ​algoritmului lui Dijkstra(pentru a obţine drumul ​de cost minim pentru toate perechile de noduri) ar fi mai rapidă decât algoritmul Floyd-Warshall.+
  
  
-===== 7.Referințe ​====== +===== 6. Referințe ===== 
-    - [[https://​en.wikipedia.org/​wiki/​Dijkstra'​s_algorithm|Algoritmul lui Dijkstra]] +  - [[https://​en.wikipedia.org/​wiki/​Minimum_spanning_tree|Minimum spanning tree]] 
-    - [[https://​en.wikipedia.org/​wiki/​Bellman%E2%80%93Ford_algorithm|Algoritmul lui Bellman Ford]] +  - [[https://​en.wikipedia.org/​wiki/​Kruskal%27s_algorithm|Algoritmul lui Kruskal]] 
-    - [[http://www.algorithmist.com/index.php/Floyd-Warshall'​s_Algorithm|Algoritmul lui Floyd-Warshall]] +  - [[https://en.wikipedia.org/wiki/Prim%27s_algorithm|Algoritmul lui Prim]] 
-    - [[https://profs.info.uaic.ro/~busaco/teach/​courses/​net/​docs/​protocoale_rutare.pdf|Protocoale de rutare]] +  - [[http://www.bogdanturcanu.ro/spanning-tree-protocol-stp/|Protocolul STP]] 
-    - [[http://example.com|Link extern]]+  - [[https://en.wikipedia.org/​wiki/​Image_segmentation|Segmentarea de imagini]]
laboratoare/laborator-07.txt · Ultima modificare: 2018/02/25 20:45 de către mihai.iacov