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.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

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.1491046139.txt.gz · Ultima modificare: 2017/04/01 14:28 de către mihai.iacov