laboratoare:laborator-07

Aceasta e o versiune anterioară a paginii.

Cuprins

Laborator 07: Parcurgerea grafurilor

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.0 Conexitate în grafuri

Componentă conexă

Graf neorientat conex

Graf orientat slab conex

Graf orientat tare conex

2.1 Costul unei muchii

2.2 Costul unui drum; drumul de cost minim

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.1489883871.txt.gz · Ultima modificare: 2017/03/19 02:37 de către mihai.iacov