Skip to content

Algoritmul Bellman-Ford in java

Algoritmul Bellman-Ford in java pentru graf orientat folosind matricea de tranzitii
Algoritmul Bellman Ford (de pe wikipedia)

procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices and edges,
   // and fills two arrays distance and predecessor with shortest-path information

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"

o varianta de implementare in java:

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
94
95
96
97
98
99
100
101
102
package Namir;
 
public class BellmanFord {
 
	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];
 
		// alocam spatiu pentru a tine minte nodurile anterioare, ca si
		// legatura, pentru un nod
		int[] predecesor = new int[nr_noduri];
 
		// presupunem ca intre noduri este distanta mare, infinit de mare :)
		for (int i = 0; i < nr_noduri; i++) {
			distance[i] = infinit;
		}
 
		// totusi, pentru nodul de inceput, nu avem distanta deloc.
		distance[inceput] = 0;
 
		// bellman ford
		// repetam de nr_noduri - 1 ori
		for (int r = 0; r < nr_noduri - 1; r++) {
			// 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++) {
					if (distance[i] + matrice[i][j] < distance[j]) {
						distance[j] = distance[i] + matrice[i][j];
						predecesor[j] = i;
					}
				}
 
			}
		}
		System.out.printf("drumul minim intre nodul %d si nodul %d are valoarea: %d\n", inceput, sfarsit, distance[sfarsit]);
		System.out.printf("si este format din:\n%d->", inceput);
 
		int[] afisare = new int[nr_noduri];
		int indexAfisare = 0, i = sfarsit;
		while (predecesor[i] != 0) {
			afisare[indexAfisare++] = i;
			i = predecesor[i];
		}
		afisare[indexAfisare] = i;
		for (i = indexAfisare; i > -1; i--) {
			System.out.printf("%d->", afisare[i]);
		}
	}
}