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:

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]);
		}
	}
}