弗洛伊德算法

算法思路

弗洛伊德算法比起迪杰斯特拉算法不一样，它比迪杰斯特拉多了一个循环。

迪杰斯特拉算法是求一个固定起点到其他点的最短路径 弗洛伊德算法是求图中任何点的两点间的最短路径。

算法的核心：

for (k=0;k<n;k++){
           for (i=0;i<n;i++){
               for (j=0;j<n;j++){
                   //弗洛伊德算法是为了改写长度
                   if (e[i][j]>e[i][k]+e[k][j]){
                       //改变长度
                       e[i][j] = e[i][k]+e[k][j];
                   }
               }
           }
       }

算法实现

package com.dwx.passage2;

public class Floyd {
    //这里我们写一个弗洛伊德算法
    //弗洛伊德算法属于是比较好理解好学的算法了
    //这里我们用e数组来存放一个二维图
    private int e[][];
    int inf = 99999999;

    public int[][] getE() {
        return e;
    }

    public void setE(int[][] e) {
        this.e = e;
    }

    //编写弗洛伊德算法
    public void floyd(){

        //n指的是点的个数
        int n = e.length;
        //弗洛伊德算法的核心
        //弗洛伊德算法的核心是三重循环
        int i,j,k;
        for (k=0;k<n;k++){
            for (i=0;i<n;i++){
                for (j=0;j<n;j++){
                    //弗洛伊德算法是为了改写长度
                    if (e[i][j]>e[i][k]+e[k][j]){
                        //改变长度
                        e[i][j] = e[i][k]+e[k][j];
                    }
                }
            }
        }


    }


}

算法实现

import com.dwx.passage2.Floyd;

import java.util.Scanner;

public class floydTest {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入有几个点:");
        int n = scanner.nextInt();
        int[][] a = new int[n][n];
        //我们已经是彻底改变为0的初始化了
        //下边我们读入边的关系 我们写一个有向图的吧
        System.out.print("请输入边数:");
        int m =scanner.nextInt();
        int inf = 99999999;
        //先对其进行初始化 要求i=j为0 其余为无穷
        int z ,h;
        for (z=0;z<n;z++){
            for (h=0;h<n;h++){
                if (z==h){
                    a[z][h] = 0;
                }else {
                    a[z][h] = inf;
                }
            }
        }


        for (int i = 1;i <= m;i++){
            System.out.print("输入点a:");
            int x = scanner.nextInt();
            System.out.print("输入b:");
            int y = scanner.nextInt();
            System.out.print("输入边长");
            int l = scanner.nextInt();
            a[x-1][y-1] = l;
        }
        for (int[] ints : a) {
            for (int anInt : ints) {
                if (anInt!=inf)
                    System.out.print(anInt+"\t");
                else
                    System.out.print("inf"+"\t");
            }
            System.out.println();
        }
        System.out.println("===============================");

        //调用弗洛伊德算法进行处理
        Floyd floyd = new Floyd();
        floyd.setE(a);
        floyd.floyd();
        int[][] e = floyd.getE();
        for (int[] ints : e) {
            for (int anInt : ints) {
                if (anInt!=inf)
                    System.out.print(anInt+"\t");
                else
                    System.out.print("inf"+"\t");
            }
            System.out.println();
        }

    }
}

Donate