Pornind de la matricea de adiacenta a unui graf M, putem construi matricea drumurilor D folosind algoritmul Roy-Warshall (wikipedia)
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
dist[v][v] ← 0
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
if dist[i][k] + dist[k][j] < dist[i][j] then
dist[i][j] ← dist[i][k] + dist[k][j]
O implemetare in java este:
package Namir;
public class RoyWarshall {
/**
* Determinare drumului minim in graf orientat folosind alhoritmul Roy-Warshall
*/
public static void main(String[] args) {
int[][] matrice; // retinem o matrice
int nr_noduri = 6;
matrice = new int[nr_noduri][nr_noduri]; // matricea retinuta este atat
// de mare
int infinit = 500;
// initializare matrice
for (int i = 0; i < nr_noduri; i++) {
for (int j = 0; j < nr_noduri; j++) {
matrice[i][j] = infinit;
if (i == j) {
matrice[i][j] = 0; // diagonala principala;
}
}
}
// am ales un graf cu 6 noduri, l-am desenat pe hartie :)
// si am trasat cateva legaturi intre noduri
// construim legaturile grafului
// aceste legaturi se mai numesc si "matricea tranzitiilor"
matrice[0][1] = 2; // avem legatura de la nodul 0 la nodul 1 de valoare 2
matrice[0][2] = 8; // avem legatura de la nodul 0 la nodul 2 de valoare 8
matrice[1][0] = 2;
matrice[1][2] = 3;
matrice[1][3] = 8;
matrice[2][0] = 8;
matrice[2][1] = 4;
matrice[2][3] = 5;
matrice[2][4] = 2;
matrice[3][1] = 8;
matrice[3][2] = 5;
matrice[3][4] = 3;
matrice[3][5] = 3;
matrice[4][2] = 2;
matrice[4][3] = 1;
matrice[4][5] = 4;
matrice[5][3] = 3;
matrice[5][4] = 4; // avem legatura de la nodul 5 la nodul 4 de valoare 4
// afisarea matricii tranzitiilor
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");
}
// dorim sa cautam drumul de la nodul 0 la nodul 5
int inceput = 0;
int sfarsit = 5;
// alocam spatiu pentru calculul distantei intre noduri
int[][] distance = new int[nr_noduri][nr_noduri];
// initializam matricea distanta
// aceasta coincide cu matricea tranzitiilor
// infinit daca nu este legatura;
// 0 daca e cazul legaturii de la nodul 1 la nodul 1; sau de la 2 la 2
// o valoare daca este legatura de la nodul i la nodul j
for (int i = 0; i < nr_noduri; i++)
for (int j = 0; j < nr_noduri; j++)
distance[i][j] = matrice[i][j];
// Roy Warshall
// repetam de nr_noduri
for (int k = 0; k < nr_noduri; k++) {
// luam la rand toate liniile
for (int i = 0; i < nr_noduri; i++) {
// luam la rand toate coloanele
for (int j = 0; j < nr_noduri; j++) {
// daca distanta intre 2 noduri i si j este mai mare decat
// distanta intre i si k plus distanta intre k si j
// sau cu alte cuvinte, daca gasim un alt drum intre i si j, de valoare mai mica
// atunci il vom "tine minte"
if (distance[i][k] + distance[k][j] < distance[i][j]) {
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}
}
System.out.printf("drumul minim intre nodul %d si nodul %d are valoarea: %d\n", inceput, sfarsit, distance[inceput][sfarsit]);
}
}