【连载】Floyd求最短路径算法设计 — Java版

Floyd求最短路径算法设计

废话不多说，直接上代码。

算法实现

• Floyd.java

package zychaowill.datastructure.graph.algo.impl;

import java.util.Arrays;

import zychaowill.datastructure.graph.algo.ShortestPathStrategy;
import zychaowill.datastructure.graph.algo.ShortestResult;
import zychaowill.datastructure.graph.vo.Graph;
import zychaowill.datastructure.graph.vo.Vertex;

public class Floyd implements ShortestPathStrategy {

    private final int MAX_VALUE = 99999999;
    private int[][] A;
    private int[][] path;
    private int MAXV;

    @Override
    public ShortestResult shortestPath(Graph graph, Vertex v) {
        init(graph);

        for (int k = 0; k < MAXV; k++) {
            for (int i = 0; i < MAXV; i++) {
                for (int j = 0; j < MAXV; j++) {
                    if (A[i][k] + A[k][j] < A[i][j]) {
                        A[i][j] = A[i][k] + A[k][j];
                        path[i][j] = k;
                    }
                }
            }
        }

        return new ShortestResult(A);
    }

    private void init(Graph graph) {
        this.A = graph.getEdges();
        this.MAXV = A.length;
        this.path = new int[MAXV][MAXV];

        for (int i = 0; i < MAXV; i++) {
            Arrays.fill(path[i], -1);
        }
    }   
}

• Graph.java添加如下方法

    public void getShortestPath() {
        shortestPathStrategy.shortestPath(this, null).printAllResult();
    }

• ShortestResult.java代码修改如下

package zychaowill.datastructure.graph.algo;

import java.util.Queue;

import zychaowill.datastructure.graph.vo.Vertex;

public class ShortestResult {

    int[][] A;
    Queue<Vertex> vertexs;
    int path;

    public ShortestResult(int[][] a) {
        A = a;
    }

    public ShortestResult(Queue<Vertex> vertexs, int path) {
        this.vertexs = vertexs;
        this.path = path;
    }

    public void printResult() {
        final String separator = " -> ";
        StringBuilder builder = new StringBuilder("");

        while (!vertexs.isEmpty()) {
            builder.append(vertexs.poll().getName() + separator);
        }

        String shortestPath = builder.substring(0, builder.lastIndexOf(separator));
        System.out.println(shortestPath + ", length: " + path);
    }

    public void printAllResult() {
        final String separator = " -> ";
        StringBuilder builder;

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[i].length; j++) {
                if (i == j) {
                    continue;
                }
                builder = new StringBuilder("");
                builder.append(i).append(separator).append(j).append(", length: ").append(A[i][j]);
                System.out.println(builder.toString());
            }
        }
    }
}

• 测试：FloydShortestPath.java

package zychaowill.datastructure.graph.examples;

import java.util.ArrayList;
import java.util.List;

import zychaowill.datastructure.graph.algo.impl.Floyd;
import zychaowill.datastructure.graph.vo.Graph;
import zychaowill.datastructure.graph.vo.Vertex;

public class FloydShortestPath {

    public static void main(String[] args) {
        List<Vertex> vertexs = new ArrayList<Vertex>();
        Vertex a = new Vertex("0", 0);
        Vertex b = new Vertex("1");
        Vertex c = new Vertex("2");
        Vertex d = new Vertex("3");
        Vertex e = new Vertex("4");
        Vertex f = new Vertex("5");
        Vertex g = new Vertex("6");
        vertexs.add(a);
        vertexs.add(b);
        vertexs.add(c);
        vertexs.add(d);
        vertexs.add(e);
        vertexs.add(f);
        vertexs.add(g);
        int[][] edges = { { 0, 4, 6, 6, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE },
                { Integer.MAX_VALUE, 0, 1, Integer.MAX_VALUE, 7, Integer.MAX_VALUE, Integer.MAX_VALUE },
                { Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 2, 6, 4, Integer.MAX_VALUE },
                { Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 5, Integer.MAX_VALUE },
                { Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 6 },
                { Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 1, 0, 8 },
                { Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE }
        };

        Graph graph = new Graph(vertexs, edges);
        graph.setShortestPathStrategy(new Floyd());
        graph.getShortestPath();
    }
}

• 测试结果:
  

Floyd求最短路径算法设计完成。完整代码，可以到我的Github仓库下载