Clasa a XI-a · 6 algoritmiRead in English
Grafuri orientate și drumuri minimeDirected graphs and shortest paths
Toți algoritmii din capitolul „Grafuri orientate și drumuri minime”, din programa de liceu: ideea explicată, complexitatea, exemple și cod C++ pe care îl poți modifica și rula chiar aici.
- 6algoritmi
- 7capitole
- 1clasă
6 algoritmi
0%
Grafuri orientate și drumuri minime
Directed graphs and shortest paths · 6 algoritmi
- Componentele tare conexeStrongly connected componentsUn graf orientat este tare conex dacă pentru oricare două noduri x și y există drum de…
- Drumuri minime de la un nod (algoritmul lui Dijkstra)Shortest paths from one node (Dijkstra's algorithm)Se cere costul minim al drumului de la nodul s la fiecare alt nod, când toate costurile…
- Gradele interne și externeIn-degrees and out-degreesÎntr-un graf orientat muchiile au sens și se numesc arce: arcul (x, y) pleacă din x și…
- Matricea drumurilor (algoritmul Roy-Warshall)Reachability matrix (Roy-Warshall algorithm)Matricea drumurilor are d[i][j] = 1 dacă există un drum (de lungime cel puțin 1) de la i…
- Drumuri minime între toate perechile de noduri (Roy-Floyd)Shortest paths between all pairs of nodes (Roy-Floyd)Fiecare arc (x, y) are un cost c ≥ 0. Matricea costurilor d pornește cu d[i][i] = 0,…
- Sortarea topologicăTopological sortArcul (x, y) înseamnă „x trebuie făcut înaintea lui y”. O sortare topologică este o…