作者:年轻人创事业的美丽家园 | 来源:互联网 | 2023-06-01 15:25
***Warshall算法*计算举证传递闭包,就可以看图有没有通路*Rij(k)Rij(k)|Rik(k-1)&&Rkj(k-1)**O(n^3)**@authorc
/**
* Floyd算法
* 计算完全最短路径
* k >= 0, Dij(0) = Wij, Dij(k) = min{Dij(k-1), Dik(k-1) +Dkj(k-1)}
*
* O(n^3)
* @author chenxuegui
*
*/
public class Floyd
{
static final int max = 10000;
public static void main(String[] args)
{
int[][] n = new int[][] { { 0, max, 3, max }, { 2, 0, max, max },
{ max, 7, 0, 1 }, { 6, max, max, 0 } };
warshall(n);
}
/**
*
* @param n
*/
public static void warshall(int[][] n)
{
for (int k = 0; k {
print(n);
for (int i = 0; i {
for (int j = 0; j {
n[i][j] = Math.min(n[i][j], n[i][k] + n[k][j]);
}
}
}
print(n);
}
public static void print(int[][] n)
{
for (int i = 0; i {
for (int j = 0; j {
if (n[i][j] >= 10000)
{
System.out.print("max ");
}
else
{
System.out.print(n[i][j] + " ");
}
}
System.out.println();
}
System.out.println();
}
}