/**
 * Algorytm Forda-Bellmana wyznaczania najkrótszej ścieżki od
 * danego wierzcholka do wszystkich pozostalych w grafie skierowanym
 * www.algorytm.org
 * (c)2005 Tomasz Lubinski 
 */
public class Ford {
	
	private static final int nieskonczonosc = 100000;

	public static void main(String[] args) {

		int	n; //liczba wierzcholkow
		int	A[][];
		int D[];
		String s;
		int	i,j,k;
		int	N;
		
		System.out.println("Podaj liczbę wierzcholkow");
		n = Console.readInt("?");
		D = new int[n];
		A = new int[n][];
		for (j=0;j<n;j++) {
			A[j] = new int[n];
		}

		System.out.println("Podaj wagi krawędzi, * oznacza nieskonczonosc");
		for (j=0;j<n;j++)
			for (i=0;i<n;i++) {
				s = Console.readString("A["+j+", "+i+"]=");
				if (s.compareTo("*")!=0)
					A[j][i]=Integer.parseInt(s);
				else
					A[j][i]=nieskonczonosc;
			}

		for (i=0;i<n;i++) D[i]=A[0][i];
		//	Przyjmujemy, że s=1, szukamy więc najkrótszych dróg od wierzchołka 1 do pozostałych
		for (k=1;k<=n-2;k++) {
			for (i=1;i<n;i++)
				for (j=0;j<n;j++) {
					if (D[j]+A[j][i]>nieskonczonosc)
						N=nieskonczonosc; 
					else
						N=D[j]+A[j][i];
					D[i]=Math.min(D[i],N);
				}
		}
		k=nieskonczonosc;
		for (i=0;i<n;i++)
			if (D[i]<k)
				System.out.println("D("+i+")=" + D[i]);
			else
				System.out.println("D("+i+")=*");

	}
}