最短路径

最短路径

加权有向图的最短路径

地址: 整合为JUI程序(Java 8+)

1. 加权有向边API

/**
 * 加权有向边API
 * v -> w
 */
public class DirectedEdge {
    private double weight;  //边的权重
    private int v;          //边的起点
    private int w;          //边的终点

    public DirectedEdge(int v, int w,double weight) {
        this.weight = weight;
        this.v = v;
        this.w = w;
    }
    //有向边的权重
    public double weight(){ return weight; }
    public int from(){ return v; }
    public int to(){ return w; }
    public String toString(){ return v +"->" + w + " " + weight; }
}

2.加权有向图API

/**
 * 加权有向图API
 */
public class EdgeWeightDiGraph {
    private int v;  //顶点数
    private int e;  //边数
    private LinkedList<DirectedEdge>[] adj;   //邻接表
    //含有v个顶点的空有向图
    public EdgeWeightDiGraph(int v) {
        this.v = v;
        e = 0;
        adj = (LinkedList<DirectedEdge>[]) new LinkedList[v];
        for(int i=0;i<v;++i)
            adj[i] = new LinkedList<>();
    }
    //从输入流中读取创建一幅图
    public EdgeWeightDiGraph(InputStream input) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(input));
        String value = null;
        try {
            int v = Integer.parseInt(reader.readLine());
            this.v = v;
            adj = (LinkedList<DirectedEdge>[]) new LinkedList[v];
            for(int i = 0 ; i < v;i++)
                adj[i] = new LinkedList<>();
            int e = Integer.parseInt(reader.readLine());
            double weight = 1;
            for(int i=0; i<e; i++){
                String[] str = reader.readLine().split(" +");
                if(str.length == 3)
                    weight = Double.parseDouble(str[2]);
                addEdge(new DirectedEdge(Integer.parseInt(str[0]),Integer.parseInt(str[1]),weight));
            }

        } catch (IOException e1) {
            e1.printStackTrace();
        } finally {
            try {
                reader.close();
            } catch (IOException e1) {
                e1.printStackTrace();
            }
        }
    }
    //顶点总数
    public int V(){ return v; }
    //边的总数
    public int E(){ return e; }
    //添加一条有向边
    public void addEdge(DirectedEdge e){
        adj[e.from()].add(e);
        ++this.e;
    }
    //从顶点v指出的所有边
    public Iterable<DirectedEdge> adj(int v){ return adj[v]; }
    //该图中的所有边
    public Iterable<DirectedEdge> edges(){
        ArrayDeque<DirectedEdge> queue = new ArrayDeque<>();
        for(int i=0;i<v;++i)
            adj[i].forEach(queue::add);
        return queue;
    }
    //图的字符串表示
    public String toString(){
        String s = v + " vertices, " + e + " edges\n";
        for(int i=0;i<v;++i){
            s += i + ": ";
            for(DirectedEdge e : adj[i])
                s += e +", ";
            s += "\n";
        }
        return s;
    }
}

3.Dijkstra算法

/**
 * Dijkstra算法
 * 概述: 使用索引优先队列优化(快速取出最小边),无法处理负权环,单源最短路径算法
 *      负权边: 标准的Dijkstra算法无法处理负权边
 *             此例允许重入队,可以处理负权边,但是如果在终点出队以后终止查询,则不能处理负权边
 * 思想:与Prim算法思想类似,(依据的权重(计算方式)不同)
 * 步骤: 从起点s开始,找出所有s指向的顶点入队,找出权重最小者(适合优先队列保存),s-v,即为s->v的最短边,
 *      然后找出s和v顶点指向其他顶点的边入队(s的已入队),找出权重最下者,又更新一条最短边,重复即可
 *
 * 改进(A*算法思想): 权重只和起点有关,在我们知道起点和终点的情况下,如果能预估到当前查询顶点到终点的权重,
 *       我们可以获取到起点然后经过当前点再到终点的总权重,依此权重生成优先队列,然后依此优先队列顺序进行放松操作
 *       可以更快速的找到终点,一般适合二维平面中起点和终点最短路径的查找(可以估算到达终点的距离)
 */
public class DijkstraSP {
    private DirectedEdge[] edgeTo;  //维护到达当前顶点的最短路径的边,索引为顶点,值为到达此顶点的边
    private double[] distTo;        //距离起点s的总权重,索引为顶点,值为权重
    private IndexMaxPQ<Double> pq;  //索引优先队列,维护将要放松的边

    //private ArrayDeque<Integer> queue;    //可以使用队列,但是此时相当于BellmanFord算法

    public DijkstraSP(EdgeWeightDiGraph g,int s) {
        edgeTo = new DirectedEdge[g.V()];
        distTo = new double[g.V()];
        Arrays.fill(distTo,Double.POSITIVE_INFINITY);
        distTo[s] = 0.0;

        pq = new IndexMaxPQ<>(g.V(),(x,y) -> -x.compareTo(y));  //创建索引优先队列,传入比较器
        pq.insert(s,0.0);   //起点放入索引优先队列中
        while(!pq.isEmpty()) relax(g,pq.delMax());  //每次都放松最小的边
        /**上可以添加终点出队后终止循环,此时不能处理负权边*/

        //使用队列: 相当于BellmanFord算法
        //queue = new ArrayDeque<>();
        //queue.offer(s);
        //while(!queue.isEmpty()) relax(g,queue.poll());

    }
    //放松操作
    private void relax(EdgeWeightDiGraph g,int v){
        for(DirectedEdge e : g.adj(v)){
            int w = e.to();
            if(distTo[w] <= distTo[v] + e.weight()) continue; //到达顶点w的总权重更小,跳过
            distTo[w] = distTo[v] + e.weight(); //否则更新顶点w的总权重
            edgeTo[w] = e; //维护到达顶点w的边
            /**在此更改权重为预估的起点到终点的值F,则可进行启发式搜索,如 F = G + H ,G=distTo[w], H为w到达终点的预估值*/
            if(pq.contains(w)) pq.change(w,distTo[w]); //维护顶点w,可重入队,因此可以处理负权边
            else pq.insert(w,distTo[w]);

            //使用队列: contains方法可能影响效率,可以额外维护一个数组用来标记是否在队列中
            //if(!queue.contains(w)) queue.offer(w);
        }
    }
    public double distTo(int v){ return distTo[v]; }
    public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY; }
    public Iterable<DirectedEdge> pathTo(int v){
        if(!hasPathTo(v)) return null;
        ArrayDeque<DirectedEdge> stack = new ArrayDeque<>();
        for(DirectedEdge x = edgeTo[v];x != null;x = edgeTo[x.from()])
            stack.push(x);
        return stack;
    }
}

4.无环加权有向图最短路径

/**
 * 加权有向无环图最短路径
 * 概述: 按照拓扑排序的顺序放松顶点即可,效率最高
 */
public class AcyclicSP {
    private DirectedEdge[] edgeTo;  //维护路径
    private double[] distTo;        //维护权重

    public AcyclicSP(EdgeWeightDiGraph g,int v) {
        edgeTo = new DirectedEdge[g.V()];
        distTo = new double[g.V()];
        Arrays.fill(distTo,Double.POSITIVE_INFINITY);
        distTo[v] = 0.0;
        TopoOrder topo = new TopoOrder(g);  //对加权有向无环图进行拓扑排序
        topo.order().forEach(e -> relax(g,e));  //按照拓扑排序顺序进行放松顶点
    }
    //松弛操作
    private void relax(EdgeWeightDiGraph g,int v){
        for(DirectedEdge e : g.adj(v)) {
            int w = e.to();
            if(distTo[w] < distTo[v] + e.weight()) continue;
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
        }
    }
    //起点到达该顶点的路径总权重
    public double distTo(int v){ return distTo[v]; }
    //是否存在路径
    public boolean hasPathTo(int v){ return distTo[v] != Double.POSITIVE_INFINITY; }
    //路径
    public Iterable<DirectedEdge> pathTo(int v){
        if(!hasPathTo(v)) return null;
        ArrayDeque<DirectedEdge> stack = new ArrayDeque<>();
        for(DirectedEdge e = edgeTo[v];e!=null;e = edgeTo[e.from()])
            stack.push(e);
        return stack;
    }
}

4.1.无环加权有向图拓扑排序

/**
 * 无环加权有向图的拓扑排序
 * 概述: 即图的深度优先搜索的逆后序排列,另见有向图
 */
public class TopoOrder {
    private boolean[] marked;   //标记遍历过的顶点
    private boolean[] onStack;  //标记递归进入的顶点,当有内层顶点指向外层顶点的边时,形成环
    private ArrayDeque<Integer> stack;  //维护拓扑排序: 出栈顺序
    public TopoOrder(EdgeWeightDiGraph g) {
        marked = new boolean[g.V()];
        onStack = new boolean[g.V()];
        stack = new ArrayDeque<>();
        for(int i=0;i<g.V();++i)
            if(!marked[i]) dfs(g,i);
    }
    public void dfs(EdgeWeightDiGraph g,int v){
        marked[v] = true;
        onStack[v] = true;  //标记递归进入
        for(DirectedEdge e : g.adj(v))
            if(!marked[e.to()]) dfs(g,e.to());
            else if(onStack[e.to()]) throw new RuntimeException("存在有向环,无法拓扑排序");
        stack.push(v);      //后续放入栈中即为逆后序
        onStack[v] = false; //递归结束取消顶点标价
    }
    public Iterable<Integer> order(){ return stack; }
}

5.BellmanFord算法普通版本

/**
 * BellmanFord算法普通版本
 * 概述: 无法处理负权环,有很多无效的放松操作,因此可对此进行优化
 * 步骤: 放松所有边E,然后重复V轮即可(V为顶点总数)
 *      其中边总数E为所有顶点v的adj(v)的和
 * 简单思考: 先考虑放松一轮,此时必定维护好起点s开始的一条边,此边为最短路径上的其中一条边,
 *          然后进行第二轮放松,此时在上一轮基础上又能维护好与上一条边相连的一条边,依次类推
 *          放松所有顶点即可
 */
public class BellmanFordCom {
    private DirectedEdge[] edgeTo;  //维护到达当前顶点的最短路径的边,索引为顶点,值为到达此顶点的边
    private double[] distTo;        //距离起点s的总权重,索引为顶点,值为权重

    public BellmanFordCom(EdgeWeightDiGraph g, int s) {
        edgeTo = new DirectedEdge[g.V()];
        distTo = new double[g.V()];
        Arrays.fill(distTo,Double.POSITIVE_INFINITY);
        distTo[s] = 0.0;
        for(int i=0;i<g.V();++i)        //放松V轮
            for(int j=0;j<g.V();++j)    //所有顶点v进行adj(v)即所有边E
                relax(g,j);
    }

    //放松操作
    private void relax(EdgeWeightDiGraph g, int v){
        for(DirectedEdge e : g.adj(v)){
            int w = e.to();
            if(distTo[w] <= distTo[v] + e.weight()) continue; //到达顶点w的总权重更小,跳过
            distTo[w] = distTo[v] + e.weight();     //否则更新顶点w的总权重
            edgeTo[w] = e;      //维护到达顶点w的边
        }
    }
    //起点s到达指定顶点的路径总权重
    public double distTo(int v){ return distTo[v]; }
    //是否存在最短路径
    public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY; }
    //返回最短路径
    public Iterable<DirectedEdge> pathTo(int v){
        if(!hasPathTo(v)) return null;
        ArrayDeque<DirectedEdge> stack = new ArrayDeque<>();
        for(DirectedEdge x = edgeTo[v];x != null;x = edgeTo[x.from()])
            stack.push(x);
        return stack;
    }
}

6.BellmanFord算法

/**
 * BellmanFord算法
 * 概述: 可以处理负权边,无法处理负权环,单源最短路径算法
 *       从BellmanFord普通版本可以看出,有很多无效的放松操作,
 *       第一轮放松操作实际上只更新了起点开始边指向的顶点,第二轮放松操作在此基础上,向外扩张
 *       因此可以使用队列保存需要放松的顶点,然后进行relax操作即可
 */
public class BellmanFordSP {
    private double[] distTo;    //维护当前顶点v到达起点s的总权重,索引为当前顶点v,值为权重
    private DirectedEdge[] edgeTo;  //维护指向该达顶点的边,索引为顶点,值为边
    private boolean[] onQ;      //标记是否已经入队
    private Queue<Integer> queue;   //队列,维护需要放松的顶点
    private int cost;           //标记放松操作的次数,
    private Iterable<DirectedEdge> cycle;

    public BellmanFordSP(EdgeWeightDiGraph g,int s) {
        distTo = new double[g.V()];
        edgeTo = new DirectedEdge[g.V()];
        onQ = new boolean[g.V()];
        queue = new ArrayDeque<>();
        Arrays.fill(distTo,Double.POSITIVE_INFINITY);
        distTo[s] = 0.0;
        queue.offer(s);
        while(!queue.isEmpty() && !hasNegativeCycle()){
            int v = queue.poll();
            onQ[v] = false;
            relax(g,v);
        }
    }
    private void relax(EdgeWeightDiGraph g, int v){
        for(DirectedEdge e : g.adj(v)){
            int w = e.to();
            if(distTo[w] <= distTo[v] + e.weight()) continue;
            distTo[w] = distTo[v] + e.weight();
            edgeTo[w] = e;
            if(!onQ[w]) {   //不在队列中入队,已经在队列中的,只更新权重和边即可
                queue.offer(w);
                onQ[w] = true;
            }
            if(cost++ % g.V() == 0) {   //负权环检测
                findNegativeCycle();
                if(hasNegativeCycle()) return;
            }
        }
    }
    //返回到达顶点v的总权重
    public double distTo(int v){ return distTo[v]; }
    public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY; }
    public Iterable<DirectedEdge> pathTo(int v){
        ArrayDeque<DirectedEdge> stack = new ArrayDeque<>();
        for(DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[v])
            stack.push(e);
        return stack;
    }
    //查找负权环
    private void findNegativeCycle(){
        int v = edgeTo.length;
        EdgeWeightDiGraph spt = new EdgeWeightDiGraph(v);
        for(int i=0;i<v;++i)
            if(edgeTo[v] != null) spt.addEdge(edgeTo[v]);   //新图spt中不会存在正权环
        EdgeWeightedDirectedCycle cfind = new EdgeWeightedDirectedCycle(spt);   //有向环检测,必定为负权环
        cycle = cfind.cycle();
    }
    //是否存在负权环
    public boolean hasNegativeCycle(){ return cycle != null; }
    //返回负权环
    public Iterable<DirectedEdge> NegativeCycle() { return cycle; }
}

6.1.加权有向图中的有向环检测

/**
 * 加权有向图中的有向环
 * 概述: 与有向图的有向环检测相同,使用深度优先搜索检测
 *       即递归遍历的内层顶点连接到外层顶点时,形成有向环
 */
public class EdgeWeightedDirectedCycle {
    private boolean[] marked;   //标记是否遍历,索引为顶点
    private DirectedEdge[] edgeTo; //维护指向当前顶点的边,索引为顶点,值为指向该顶点的边
    private boolean[] onStack;     //维护递归进入的顶点
    private ArrayDeque<DirectedEdge> cycle; //维护有向环

    public EdgeWeightedDirectedCycle(EdgeWeightDiGraph g) {
        marked = new boolean[g.V()];
        edgeTo = new DirectedEdge[g.V()];
        onStack = new boolean[g.V()];
        for(int i=0;i<g.V();++i)
            if(!marked[i]) dfs(g,i);
    }

    //深度优先搜索
    private void dfs(EdgeWeightDiGraph g,int v){
        marked[v] = true;
        onStack[v] = true; //递归进入时,标记
        for(DirectedEdge e : g.adj(v)){
            int w = e.to();
            if(cycle != null) return;
            if(!marked[w]){ //递归遍历没有遍历过的顶点
                edgeTo[w] = e;
                dfs(g,w);
            }
            else if(onStack[w]){    //此时有递归内层顶点指向外层顶点的边,形成环
                cycle = new ArrayDeque<>();
                while(e.from() != w){   //维护该环
                    cycle.push(e);
                    e = edgeTo[e.from()];
                }
                cycle.push(e);
                return;
            }
        }
        onStack[v] = false; //递归出去时,取消标记
    }
    //是否有环
    public boolean hasCycle(){ return cycle != null; }
    //返回加权有向环
    public Iterable<DirectedEdge> cycle(){ return cycle; }
}

7.FLoyd算法

/**
 * Floyd算法
 * 概述: 多源最短路径算法,查询结束,可以获取任意两个顶点的最短路径
 * 步骤: 对一个中转顶点k,更新任意两个顶点i,j经过该中转顶点k使得路径更短,一轮结束后
 *       那些需要k中转的最短路径必定更新完成k顶点,因此要更新最短路径所有顶点,
 *       对每个顶点都进行一轮此操作即可
 */
public class Floyd {
    private double[][] dist;    //维护权重的矩阵
    private int[][] edge;       //维护路径的矩阵(构造函数中可不做处理,判断是否存在路径是使用dist,
                                //edge中只维护好存在的路径即可,不存在的不维护不影响)
    public Floyd(EdgeWeightDiGraph g) {
        dist = new double[g.V()][g.V()];
        edge = new int[g.V()][g.V()];
        //初始化
        for(int i=0;i<g.V();++i)
            for(int j=0;j<g.V();++j) {
                edge[i][j] = -1;
                if (i == j) {
                    dist[i][j] = 0.0;
                    edge[i][j] = i;
                }
                else dist[i][j] = Double.POSITIVE_INFINITY;
            }
        //将图的信息更新到矩阵中
        for(int i=0;i<g.V();++i){
            for(DirectedEdge e : g.adj(i)) {
                dist[i][e.to()] = e.weight();
                edge[i][e.to()] = i;
            }
        }
        floyd();
    }

    //floyd算法
    private void floyd(){
        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]) continue;
                    dist[i][j] = dist[i][k] + dist[k][j];   //更新权重
                    edge[i][j] = edge[k][j];                //更新路径:i-j更新为i-k-j;
                }
    }

    public double disTo(int s,int v){ return dist[s][v];}
    public boolean hasPathTo(int s,int v){ return dist[s][v] < Double.POSITIVE_INFINITY; }
    public Iterable<Integer> pathTo(int s,int v){
        if(!hasPathTo(s,v)) return null;
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for(int i=v;i!=s;i=edge[s][i])
            stack.push(i);
        stack.push(s);
        return stack;
    }
}