Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare | Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-07 [2017/04/02 16:06] mihai.iacov [6.Exiciții laborator] |
laboratoare:laborator-07 [2017/04/02 16:08] mihai.iacov [6.Exiciții laborator] |
||
---|---|---|---|
Linia 198: | Linia 198: | ||
- Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite. | - Daţi un exemplu de graf orientat cu un singur arc cu cost negativ pentru care algoritmul lui Dijkstra dă rezultate greşite. | ||
- | - Cum putem folosi algoritmul lui Dijkstra pentru a obţine aceleaşi rezultate ca algoritmul Floyd-Warshall(drumul de cost minim pentru toate perechile de noduri). Daţi un exemplu în care această folosire ar fi mai rapidă decât algoritmul Floyd-Warshall. | + | - Cum putem folosi algoritmul lui Dijkstra pentru a obţine aceleaşi rezultate ca algoritmul Floyd-Warshall(drumul de cost minim pentru toate perechile de noduri). |
- 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/ | - 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/ | ||
- Verificaţi dacă un graf conţine cicluri negative. | - Verificaţi dacă un graf conţine cicluri negative. | ||
Linia 207: | Linia 207: | ||
- Aceeaşi întrebare dacă înmulţim fiecare cost cu 100. | - Aceeaşi întrebare dacă înmulţim fiecare cost cu 100. | ||
- 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? | - 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. | ||