Warshall算法（用法详解，并转换成代码的形式）-Toy模板网

这篇具有很好参考价值的文章主要介绍了Warshall算法（用法详解，并转换成代码的形式）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

关于Warshall算法，我先通过离散数学中求传递闭包来解释他的使用规则。

一般的，给定一个矩阵A（行列相等），我们对其使用Warshall算法：

//注，该矩阵上只有0或1两种元素，做加法时，1+1还是1

1、先找到该矩阵的对角线，并从对角线的左上方开始为第一个元素

2、以对角线上第一个元素为中心，按列展开，寻找中心所在的列中所有不为0的元素

3、将“ 该中心所在的行 ”加到“ 该中心所在的列 ”中所有不为0的元素所在的行上

4、加完之后，以对角线上第二个元素为中心，按列展开，寻找该列中所有不为0的元素

5、重复“ 操作3 ”

6、一直到将对角线上所有元素都展开后结束。

在此特别强调！！！一定！一定！不要对中心按行展开来求！！！

可能有一些求到的结果没有问题，但是有些情况是会求到错误的结果，原因是有些数值会被忽略

以下用离散数学的具体问题来分析：

warshall,矩阵,线性代数,java

按列展开：在对角线上的第一个元素所在的列上第一列第二行对于着（b，a），后域为a，则我们将a行加到b行上就会得到一个（b，b），这个（b，b）是怎么来的呢，R中有（b，a）和（a，b）因此他的传递闭包就会有（b，b），按照这个思路往下思考就会知道它是用什么原理解决传递闭包的问题了

传递闭包：就是R能构成传递关系的最小序偶集合

关系是序偶的集合，上边的R关系里边的元素就是序偶。

下边我们试试将其变成代码的形式：

写一个实现类

package Java_Warshall;
public class Warshall {
    int[][] num;
    public Warshall(int[][] num){
        this.num=num;
        count();
    }
    public int[][] count(){
        for(int i=0;i<num.length;i++){
            for(int j=0;j<num[i].length;j++){
                if(num[j][i]==1){   //寻找第i列第j行为1的元素
                    for(int i1=0;i1<num.length;i1++){
                        if(num[j][i1]==0&&num[i][i1]==1){  //判断j行中的各元素是否为0，和i行中的各元素是否为1
                            num[j][i1]=1;
                        }
                    }
                }
            }
        }
        return num;
    }

    public void print(){
        for(int i=0;i<num.length;i++){
            for(int j=0;j<num.length;j++){
                System.out.printf("%d ",num[i][j]);
            }
            System.out.println();
        }
    }
}

再写一个测试类

package Java_Warshall;
import java.util.*;
public class Demo {
    public static void main(String[] args) {
        int[][] num;
        Scanner s=new Scanner(System.in);
        System.out.print("请选择要输入几阶矩阵：");
        int n=s.nextInt();
        num=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                num[i][j]=s.nextInt();
            }
        }
        Warshall w=new Warshall(num);
        w.print();
    }
}

运行效果

warshall,矩阵,线性代数,java