Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
Ambele părți revizuirea anterioară Versiuni anterioare Urmatoarea versiune | Versiuni anterioare Urmatoarea versiune Ambele părți următoarea reviziune | ||
laboratoare:laborator-07 [2017/04/01 19:25] mihai.iacov [2.2 Costul unui drum; drumul de cost minim] |
laboratoare:laborator-07 [2017/04/07 16:54] iulian.matesica [6.Exiciții laborator] |
||
---|---|---|---|
Linia 1: | Linia 1: | ||
- | ====== Laborator 07: Parcurgerea grafurilor | + | ====== Laborator 07: Drumuri de cost minim ====== |
===== 1.Obiective laborator ====== | ===== 1.Obiective laborator ====== | ||
Linia 53: | Linia 53: | ||
<note tip> | <note tip> | ||
+ | <note important> | ||
+ | Pentru grafuri orientate, ne referim la vecinii la care putem ajunge printr-un arc ce pleacă din C: (C,V). | ||
+ | </ | ||
Paşii algoritmului lui Dijkstra: | Paşii algoritmului lui Dijkstra: | ||
< | < | ||
Linia 173: | Linia 176: | ||
* în aceste cazuri, nu putem pune problema găsirii drumurilor de cost minim. | * în aceste cazuri, nu putem pune problema găsirii drumurilor de cost minim. | ||
+ | </ | ||
+ | <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 tip> | <note tip> | ||
Linia 189: | Linia 195: | ||
</ | </ | ||
- | ===== 6.Exiciții laborator ====== | + | ===== 6. Exercițîi laborator ====== |
+ | |||
+ | - 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 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/ | ||
+ | - Verificaţi dacă un graf conţine cicluri negative. | ||
+ | |||
+ | ====6.1. Exerciții - schelet de laborator==== | ||
+ | Pentru acest laborator puteți descărca scheletul de cod de [[http:// | ||
+ | |||
+ | === Linux=== | ||
+ | Puteti folosi utilitarul '' | ||
+ | |||
+ | * '' | ||
+ | * '' | ||
+ | |||
+ | Pentru compilare folositi comanda '' | ||
+ | |||
+ | |||
+ | ===Extra=== | ||
+ | |||
+ | - 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 muchii, se modifică drumul de cost minim? (dacă da, daţi un exemplu; dacă nu, explicaţi de ce). | ||
+ | - 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. | ||
===== 7.Referințe ====== | ===== 7.Referințe ====== |