弗洛伊德算法怎么理解_弗洛伊德算法思想

全栈程序员-站长 • 2022年10月23日下午3:00 • 未分类 • 阅读 0

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

这个方法中，其中每一个顶点到另一个顶点最多就是两步。
所以就是找到两个顶点的最近距离

package a;

import java.lang.reflect.Array;
import java.util.Arrays;

public class FloydDemo { 
   
    public static void main(String[] args) { 
   
        char[] diots = { 
   'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] edges = new int[diots.length][diots.length];
        final int N = 65535;

        edges[0]=new int[]{ 
   0,5,7,N,N,N,2};//注意这个自身到自身的距离是0 ，并不是N 和地杰斯特拉的区别
        edges[1]=new int[]{ 
   5,0,N,9,N,N,3};
        edges[2]=new int[]{ 
   7,N,0,N,8,N,N};
        edges[3]=new int[]{ 
   N,9,N,0,N,4,N};
        edges[4]=new int[]{ 
   N,N,8,N,0,5,4};
        edges[5]=new int[]{ 
   N,N,N,4,5,0,6};
        edges[6]=new int[]{ 
   2,3,N,N,4,6,0};

        FGraph fGraph = new FGraph(diots, edges, diots.length);
        fGraph.floyd();
        fGraph.show();
    }
}

class FGraph{ 
   
    char [] data;
    int [] [] dis;
    int [][] pre;

    public FGraph(char[] data, int[][] dis, int len) { 
   
        this.data = data;
        this.dis = dis;
        pre = new int[len][len];
        for (int i = 0; i < data.length; i++) { 
   

            Arrays.fill(pre[i],i);//每个顶点的前驱节点默认值是自身的下标。和地杰斯特拉不一样，地杰斯特拉默认不初始化。
        }
    }


    public void show(){ 
   
        for (int i = 0; i < data.length; i++) { 
   
            for (int j = 0; j < data.length; j++) { 
   
                System.out.print(data[pre[i][j]]+"\t");
            }
            System.out.println();
            for (int j = 0; j < data.length; j++) { 
   
                System.out.print("("+data[i]+"-->"+data[j]+":"+dis[i][j]+"|\t");
            }
            System.out.println();
        }

    }

    public void floyd(){ 
   
        int len =0;//变量保存距离
        for (int i = 0; i < data.length; i++) { 
   //中间
            for (int j = 0; j < data.length; j++) { 
   //起点
                for (int k = 0; k < data.length; k++) { 
   //终点
                    len = dis[j][i]+dis[i][k];
                    if (len < dis[j][k]) { 
   
                        dis[j][k] = len;
                        pre[j][k] = pre[i][k];//这个是更新前一个顶点。在初始化的时候pre 的每一行都是 自身。所以，这个第一次是自身。然后变成了中间的这个点。
                    }
                }
            }
        }

    }

}