Skip to content

Determinare drumului minim in graf orientat folosind alhoritmul Roy-Warshall (java)

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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]);
	}
 
}