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-13 [2017/02/19 22:31] mihai.iacov |
laboratoare:laborator-13 [2017/02/19 23:30] mihai.iacov [1.2 Greedy vs. Dijkstra] |
||
---|---|---|---|
Linia 21: | Linia 21: | ||
| | ||
*Un candidat face parte din soluţie dacă drumul căutat trece prin el | *Un candidat face parte din soluţie dacă drumul căutat trece prin el | ||
- | | + | |
- | | + | |
| | ||
Linia 35: | Linia 35: | ||
===Dijkstra=== | ===Dijkstra=== | ||
- | funcţia de **cost potenţial** g(N) = costul minim al drumului din punctul iniţial până în nodul curent(N) | + | Definim |
+ | |||
+ | <note important> | ||
+ | |||
+ | ===Observaţii=== | ||
+ | |||
+ | *În general, nu este **necesar** şi nici **suficient** ca funcţia de cost potenţial a unui nod să fie 0 pentru ca acel nod să facă parte din soluţia finală. | ||
+ | | ||
+ | *La algoritmul lui Dijkstra, în afară de nodurile S şi D, celelalte noduri au cost potenţial nenul(excepţie dacă există muchii de cost 0). | ||
+ | |||
+ | <note warning> | ||
+ | |||
+ | ===Performanţe=== | ||
+ | |||
+ | | ||
+ | | ||
f = g + h | f = g + h |