动态规划(三,Floyd算法)

66658.jpg

概述:

Floyd算法是为了找出带权图中的多源最短路径,即从图中一个顶点到宁一个顶点权重最小的路径.

思想:

分别用二维数组p,d表示图的边和权重

如果从顶点v1到顶点v2的权重是4,从顶点v1>v0>v2的总权重是3.
那么,路径数组p中p[1][2]改为p[1][0],权重数组d中d[1][2]改为d[1][0]+d[0][2].

image.png
上面是以v0为跳板,优化了路径和权重.
那么,我们分别以每个顶点为跳板,依次做优化操作,就可以得到图的多源最短路径
image.png

最后,我们输出顶点之间的多源最短路径.
比如,从顶点v1>v3.
从最终的二维数组d和p,我们可以推到出:
倒数第一步:v1>v2
倒数第二步:v1>v0
即,路径为v1>v0>v2>v3.

代码:

import org.junit.Test;

public class Floyd {
    public static final int I = 100;
    //邻接距阵
    public static int[][] d = new int[][]{
            {0, 2, 1, 5},
            {2, 0, 4, I},
            {1, 4, 0, 3},
            {5, I, 3, 0}
    };
    public static int[][] p=new int[][]{
            {0,1,2,3},
            {0,1,2,3},
            {0,1,2,3},
            {0,1,2,3}
    };

    private void floyd(){
        for (int k = 0; k < d.length; k++) {
            for (int i = 0; i < d.length; i++) {
                for (int j = 0; j < d.length; j++) {
                    if (d[i][j]>d[k][j]+d[i][k]){
                        d[i][j] = d[k][j]+d[i][k];
                        p[i][j] = p[i][k];
                    }
                }
            }
        }
    }

    private void printShortPath(){
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d.length; j++) {
                int k = p[i][j];
                System.out.println("v"+i+">"+"v"+j+" weight:"+d[i][j]+" path: v"+i+" >v"+k);
                while (k!=j){
                    k = p[k][j];
                    System.out.println("v"+k);
                }
            }
        }
    }

    @Test
    public void test(){
        floyd();
        printShortPath();
    }

}