Floyd算法

标签：下一跳   print   splay   ati   end   ==   多源   out   弗洛伊德算法   

Floyd算法

弗洛伊德算法,用来计算多源最短路径(任意两个点之间的最短路径)

符号描述

• D(i,j)
  • 节点i到节点j的最短距离
• N(i,j)
  • 节点i到节点j的下一跳节点

思维

1. 如果某个节点位于起点到终点的最短路径上
   • D(i,j)=D(i,k)+D(k,j)
2. 如果某个节点不位于起点到终点的最短路径上
   • D(i,j)

Java

public class Floyd {
    private int [][]graph;
    private int size;
    private int[][] d;
    private int[][] n;

    public Floyd(int[][] graph) {
        this.graph = graph;
        size=graph.length;
        d=new int[size][size];
        n=new int[size][size];
        for (int i=0;i"+n[start][end];
            start=n[start][end];
        }
        result+="->"+end;
        System.out.println(result);
    }

    public static void main(String[] args) {
        int INF=Integer.MAX_VALUE/2;
        int[][] graph=new int[][]{
                {INF,-1,3,INF,INF},
                {INF,INF,3,2,2},
                {INF,INF,INF,INF,INF},
                {INF,1,5,INF,INF},
                {INF,INF,INF,INF,-3}
        };
        Floyd floyd=new Floyd(graph);
        floyd.display(0,4);
    }
}

Floyd算法

标签：下一跳   print   splay   ati   end   ==   多源   out   弗洛伊德算法   

原文地址：https://www.cnblogs.com/redo19990701/p/12821308.html