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)
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.
package Namir;
/*
* Determinarea drumul optim într-un graf / drum hamiltonian, folosind matricea de atingere. Chan
*/
public class Chan {
public static void main(String[] args) {
int[][] matrice; // retinem o matrice
int nr_noduri = 5;
matrice = new int[nr_noduri][nr_noduri]; // matricea retinuta este atat
matrice[0][1] = 1;
matrice[0][2] = 1;
matrice[0][3] = 1;
matrice[0][4] = 1;
matrice[1][2] = 1;
matrice[1][3] = 1;
matrice[1][4] = 1;
matrice[2][4] = 1;
matrice[4][3] = 1;
// afisarea matricii
System.out.printf("\nmatricea citita este:\n");
for (int i = 0; i < nr_noduri; i++) {
for (int j = 0; j < nr_noduri; j++) {
System.out.printf("%d ", matrice[i][j]);
}
System.out.printf("\n");
}
// Pentru determinarea unui drum hamiltonian într-un graf orientat şi fără circuite
// se parcurge un algoritm cu 2 pasi (Chan?!)
// Pasul 1. Se construieşte matricea conexă terminală T pornind de la matricea 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.
int[][] t = new int[nr_noduri][nr_noduri];
for (int i = 0; i < nr_noduri; i++)
for (int j = 0; j < nr_noduri; j++)
t[i][j] = matrice[i][j];
for (int i = 0; i < nr_noduri; i++) {
for (int j = 0; j < nr_noduri; j++)
if (matrice[i][j] != 0) { //daca avem drum intre nodul i si nodul j
t[i][j] = matrice[i][j];
for (int k = 0; k < nr_noduri; k++) {
t[i][k] = matrice[i][k] + t[j][k]; // 0+0=0; 0+1=1; 1+0=1; 1+1=1
if (t[i][k] > 1) // 1+1 = 2, deci vom folosi 1 in loc de 2
t[i][k] = 1;
}
}
}
// numaram numarul de elemente diferite de zero
int nrElementeNenule = 0;
for (int i = 0; i < nr_noduri; i++)
for (int j = 0; j < nr_noduri; j++)
if (t[i][j] != 0)
++nrElementeNenule;
int nrNoduriHamilton = nr_noduri * (nr_noduri - 1) / 2;
if (nrNoduriHamilton != nrElementeNenule)
System.out.printf("s-au gasit %d elemente nenule si nu avem drum hamiltonian (n(n-1)/2=%d)\n", nrElementeNenule, nrNoduriHamilton);
// Pasul 2. Din matricea T se construieşte T_prim.
// punem suma liniei din matricea t
int[][] tPrim = new int[nr_noduri][2];
for (int i = 0; i < nr_noduri; i++)
for (int j = 0; j < nr_noduri; j++) {
tPrim[i][0] = i;
tPrim[i][1] = tPrim[i][1] + t[i][j];
}
// sortam matricea rezultat ca pe un vector de obiecte cu 2 proprietati
// [0] este indexul original
// [1] este suma calculata anterior
// sortam dupa suma, deci dupa [1]
for (int i = 0; i < nr_noduri - 1; i++) {
for (int j = i + 1; j < nr_noduri; j++)
if (tPrim[i][1] < tPrim[j][1]) {
int vTemp = tPrim[i][1];
int iTemp = tPrim[i][0];
tPrim[i][1] = tPrim[j][1];
tPrim[i][0] = tPrim[j][0];
tPrim[j][1] = vTemp;
tPrim[j][0] = iTemp;
}
}
// afisam rezultatul
System.out.printf("Drumul optim folosind matricea de atingere este:\n");
for (int i = 0; i < nr_noduri; i++)
System.out.printf("%d->", tPrim[i][0] + 1);
}
}