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

Myth丶恋晨 2022-06-05 08:53 166阅读 0赞

#### 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();
        }
    }

*  测试结果:  
    ![这里写图片描述][SouthEast]

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

[SouthEast]: /images/20220605/9b4b085210ac437b98164f7e01d3db3a.png
[Github]: https://github.com/Zychaowill/AlgorithmAndDataStructure/tree/master/src/main/java/zychaowill/datastructure/graph