Pornind de la matricea de adiacenta a unui graf M, putem construi matricea drumurilor D folosind algoritmul Roy-Warshall (wikipedia)
(more…)
Tag: algoritm
-
Determinare drumului minim in graf orientat folosind alhoritmul Roy-Warshall (java)
-
Determinarea drumul optim într-un graf / drum hamiltonian, folosind matricea de atingere. (Chan)
O rezolvare pentru problema:
Să se întocmească un program care determină drumul optim într-un graf, folosind matricea de atingere.
consta in determinarea unui drum hamiltonian într-un graf orientat (fără circuite).
Se poate executa un algoritm cu 2 pasi (Chan)- Pasul 1. Se construieşte matricea conexă terminală T pornind de lamatricea tranziţiilor M.
Se determină câte elemente din T sunt nenule; dacă numărul acestora este n(n-1)/2, atunci graful conţine un drum hamiltonian.- Pasul 2. Din matricea T se construieşte T_prim.
- Pasul 1. Se construieşte matricea conexă terminală T pornind de lamatricea tranziţiilor M.
-
Algoritmul Bellman-Ford in java
Algoritmul Bellman-Ford in java pentru graf orientat folosind matricea de tranzitii
Algoritmul Bellman Ford (de pe wikipedia)
(more…)