Diferențe

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

--- laboratoare:laborator-07 [2017/04/02 15:57]
mihai.iacov [6.Exiciții laborator]
+++ laboratoare:laborator-07 [2017/04/02 16:10]
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 pentru care algoritmul lui Dijkstra lucrează mult mai uşor decât algoritmul Bellman-Ford.
+  - 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ăm la grafurile pe care merg toţi cei trei algoritmi.
   - 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.
   - Verificaţi dacă un graf conţine cicluri negative.
@@ Linia 207: / Linia 207: @@
   - 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?
+  - 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.

Structuri de Date și Algoritmi (seria 1AB)