Unelte utilizator
Bara de navigare
laboratoare:laborator-07
Aceasta e o versiune anterioară a paginii.
Cuprins
Laborator 07: Parcurgerea grafurilor
1.Obiective laborator
- Înțelegerea ideii de cost și de drum minim într-un graf
- Prezentarea algoritmilor care calculează drumul de cost minim
- Înțelegerea aplicațiilor practice prezente în:
- găsirea drumului minim între 2 locații (ex: GPS)
- rutarea în cazul rețelelor de calculatoare (ex: protocolul RIP)
2.Considerente teoretice
2.1 Costul unei muchii
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
Î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).
Costul unui drum va fi definit ca suma costurilor muchiilor ce compun acel drum.
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.
3.Drumul de cost minim cu sursă unică
3.1 Algoritmul lui Dijkstra
3.2 Algoritmul Bellman-Ford
4.Drumul de cost minim între oricare 2 noduri
4.1 Algoritmul Floyd-Warshall
5.Exiciții laborator
6.Referințe
laboratoare/laborator-07.1491046835.txt.gz · Ultima modificare: 2017/04/01 14:40 de către mihai.iacov
Exceptând locurile unde este altfel specificat, conținutul acestui wiki este licențiat sub următoarea licență: CC Attribution-Share Alike 4.0 International
