算法分析入门系列(四) 最短路径算法

单源最短路径算法

问题描述

从s点出发到达其他点的最短路径

源代码

import java.util.*;

public class ShortestPath {
    // 定义顶点Vertex类
    static class Vertex {
        private final static int infinite_dis = Integer.MAX_VALUE;
        private String name; // 节点名字
        private boolean known; // 此节点是否已知
        private int adjuDist; // 此节点距离
        private Vertex parent; // 当前从初始化节点到此节点的最短路径下的父亲节点

        public Vertex() {
            this.known = false;
            this.adjuDist = infinite_dis;
            this.parent = null;
        }

        public Vertex(String name) {
            this();
            this.name = name;
        }

        public Vertex getParent() {
            return parent;
        }

        public void setParent(Vertex parent) {
            this.parent = parent;
        }

        public boolean equals(Object obj) {
            if (this.getName() == ((Vertex) obj).getName()) {
                return true;
            }
            if (this.name == null) {
                throw new NullPointerException("name of Vertex to be compared cannot be null!");
            } else {
                return false;
            }
        }

        public static int getInfiniteDis() {
            return infinite_dis;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public boolean isKnown() {
            return known;
        }

        public void setKnown(boolean known) {
            this.known = known;
        }

        public int getAdjuDist() {
            return adjuDist;
        }

        public void setAdjuDist(int adjuDist) {
            this.adjuDist = adjuDist;
        }
    }

    static class Edge {
        // 此有向边的起始点
        private Vertex startVertex;
        // 此有向边的终点
        private Vertex endVertex;
        // 此有向边的权值
        private int weight;

        public Edge(Vertex startVertex, Vertex endVertex, int weight) {
            this.startVertex = startVertex;
            this.endVertex = endVertex;
            this.weight = weight;
        }

        public Vertex getStartVertex() {
            return startVertex;
        }

        public void setStartVertex(Vertex startVertex) {
            this.startVertex = startVertex;
        }

        public Vertex getEndVertex() {
            return endVertex;
        }

        public void setEndVertex(Vertex endVertex) {
            this.endVertex = endVertex;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

    }

    private List<Vertex> vertexList; // 图的顶点集
    private Map<Vertex, List<Edge>> ver_edgeList_map; // 图的每个顶点对应的有向边

    public ShortestPath(List<Vertex> vertexList, Map<Vertex, List<Edge>> ver_edgeList_map) {
        this.vertexList = vertexList;
        this.ver_edgeList_map = ver_edgeList_map;
    }

    public void setRoot(Vertex v) {
        v.setParent(null);
        v.setAdjuDist(0);
    }

    private void updateChildren(Vertex v) {
        if (v == null) {
            return;
        }
        if (ver_edgeList_map.get(v) == null || ver_edgeList_map.get(v).size() == 0) {
            return;
        }
        List<Vertex> childrenList = new LinkedList<Vertex>();
        for (Edge e : ver_edgeList_map.get(v)) {
            Vertex childVertex = e.getEndVertex();
            if (!childVertex.isKnown()) {
                childVertex.setKnown(true);
                childVertex.setAdjuDist(v.getAdjuDist() + e.getWeight());
                childVertex.setParent(v);
                childrenList.add(childVertex);
            }
            int nowDist = v.getAdjuDist() + e.getWeight();
            if (nowDist >= childVertex.getAdjuDist()) {
                continue;
            } else {
                childVertex.setAdjuDist(nowDist);
                childVertex.setParent(v);
            }
        }
        for (Vertex vc : childrenList) {
            updateChildren(vc);
        }
    }

    public void shortestPathTravasal(int startIndex, int destIndex) {

        Vertex start = vertexList.get(startIndex);
        Vertex dest = vertexList.get(destIndex);
        String path = "[" + dest.getName() + "]";

        setRoot(start);

        updateChildren(vertexList.get(startIndex));

        int shortest_length = dest.getAdjuDist();

        while ((dest.getParent() != null) && (!dest.equals(start))) {
            path = "[" + dest.getParent().getName() + "] --> " + path;
            dest = dest.getParent();
        }

        System.out.println("[" + vertexList.get(startIndex).getName() + "] to [" + vertexList.get(destIndex).getName()
                + "] ShortestPath shortest path: " + path);

        System.out.println("shortest length:" + shortest_length);
    }

    public static void main(String[] args) {

        Vertex s = new Vertex("s");
        Vertex t = new Vertex("t");
        Vertex x = new Vertex("x");
        Vertex y = new Vertex("y");
        Vertex z = new Vertex("z");
        List<Vertex> verList = new LinkedList<ShortestPath.Vertex>();
        verList.add(s);
        verList.add(t);
        verList.add(x);
        verList.add(y);
        verList.add(z);

        Map<Vertex, List<Edge>> vertex_edgeList_map = new HashMap<Vertex, List<Edge>>();

        List<Edge> sList = new LinkedList<ShortestPath.Edge>();
        sList.add(new Edge(s, t, 6));
        sList.add(new Edge(s, y, 7));
        List<Edge> tList = new LinkedList<ShortestPath.Edge>();
        tList.add(new Edge(t, y, 8));
        tList.add(new Edge(t, x, 5));
        List<Edge> xList = new LinkedList<ShortestPath.Edge>();
        xList.add(new Edge(x, t, -2));

        List<Edge> yList = new LinkedList<ShortestPath.Edge>();
        yList.add(new Edge(y, x, -3));
        yList.add(new Edge(y, z, 9));

        List<Edge> zList = new LinkedList<ShortestPath.Edge>();
        zList.add(new Edge(z, x, 7));
        vertex_edgeList_map.put(s, sList);
        vertex_edgeList_map.put(t, tList);
        vertex_edgeList_map.put(x, xList);
        vertex_edgeList_map.put(y, yList);
        vertex_edgeList_map.put(z, zList);

        ShortestPath g = new ShortestPath(verList, vertex_edgeList_map);
        g.shortestPathTravasal(0, 1);
        g.shortestPathTravasal(0, 2);
        g.shortestPathTravasal(0, 3);
        g.shortestPathTravasal(0, 4);
    }
}

实验结果

全点对最短路径

问题描述

单点到另外一个点的最短距离

源代码

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

/**
 * 全点对最短路径算法
 */
public class FullPointPairShortestPath {
    public static void main(String[] args) {
        List<InnerEdge> innerEdges = new ArrayList<>();
        innerEdges.add(new InnerEdge(1, 2, 3));
        innerEdges.add(new InnerEdge(1, 3, 8));
        innerEdges.add(new InnerEdge(1, 5, -4));
        innerEdges.add(new InnerEdge(2, 5, 7));
        innerEdges.add(new InnerEdge(2, 4, 1));
        innerEdges.add(new InnerEdge(3, 2, 4));
        innerEdges.add(new InnerEdge(4, 1, 2));
        innerEdges.add(new InnerEdge(4, 3, -5));
        innerEdges.add(new InnerEdge(5, 4, 6));
        int[][] dist = new int[5][5];
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist[i].length; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                    continue;
                }
                dist[i][j] = Integer.MAX_VALUE / 3;
            }
        }
        for (InnerEdge innerEdge : innerEdges) {
            dist[innerEdge.getStartIndex() - 1][innerEdge.getEndIndex() - 1] = innerEdge.getWeight();
        }
        getFullPointPairShortestPath(dist);
    }

    public static void getFullPointPairShortestPath(int[][] dist) {
        for (int k = 0; k < dist.length; k++) {
            for (int i = 0; i < dist.length; i++) {
                for (int j = 0; j < dist.length; j++) {
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        System.out.print("\t");
        for (int i = 0; i < dist.length; i++) {
            System.out.print(i + 1 + "\t");
        }
        System.out.println();
        for (int i = 0; i < dist.length; i++) {
            System.out.print(i + 1 + "\t");
            for (int j = 0; j < dist.length; j++) {
                System.out.print(dist[i][j] + "\t");
            }
            System.out.println();
        }
    }

}

/**
 * InnerEdge
 */
class InnerEdge {

    private Integer startIndex;
    private Integer endIndex;
    private Integer weight;

    public InnerEdge() {

    }

    public Integer getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(Integer startIndex) {
        this.startIndex = startIndex;
    }

    public Integer getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(Integer endIndex) {
        this.endIndex = endIndex;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }

    public InnerEdge(Integer startIndex, Integer endIndex, Integer weight) {
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.weight = weight;
    }
}

实验结果

思考题

1. 全点对最短路径算法动态规划算法范式

寻找两点间的最佳中转点

2. 图的存储方式和运算效率之间的关系

使用数组来存储更加高效，使用Java对象来存储更加清晰明了