动态规划――2 Warshall算法

/**
 * Warshall算法

 * 计算举证传递闭包，就可以看图有没有通路

 * Rij(k) = Rij(k) | Rik(k-1) && Rkj(k-1)
 * 
 * O(n^3)
 * 
 * @author chenxuegui
 * 
 */
public class Warshall
{
	public static void main(String[] args)
	{
		boolean[][] n = new boolean[][] { { false, true, false, false },
				{ false, false, false, true }, { false, false, false, false },
				{ true, false, true, false } };

		warshall(n);

	}

	/**
	 * 
	 * @param n
	 */
	public static void warshall(boolean[][] n)
	{
		for (int k = 0; k < n.length; k++)
		{

			print(n);
			for (int i = 0; i < n.length; i++)
			{
				//n[i][k]为false则n[i][j]为n[i][j]
				if (n[i][k] != false)
				{
					for (int j = 0; j < n.length; j++)
					{
						n[i][j] = n[i][j] || (n[i][k] && n[k][j]);
					}
				}
			}
		}

		print(n);
	}

	public static void print(boolean[][] n)
	{
		for (int i = 0; i < n.length; i++)
		{
			for (int j = 0; j < n.length; j++)
			{
				if (n[i][j])
				{
					System.out.print("1 ");
				}
				else
				{
					System.out.print("0 ");
				}
			}
			System.out.println();
		}

		System.out.println();
	}
}