算法-最短路径问题
标签:算法

最短路径问题(Shortest Path)

最短路径求出从一个节点到另个一节点耗费最小的那条路径,常用于解决路径规划,工作任务规划等,无向图的广度优先遍历最后得到的最短路径树(Shortest Path Tree)就是为了解决了单源最短路径(Single Source Shortest Path 图中的所有点到一个起始点的总权值最小)问题

松弛操作就是看从一个点到另一个点如果绕一下,所需的花费是不是比直接到达的更小。松弛操作是最短路径求解的核心。

1. Dijkstra 单源最短路径算法

前提是:图中不能有负权边存在的,它的时间复杂度是O(ElogV)

package com.liuyao.graph2.Dijkstra;

import com.liuyao.graph2.*;

import java.util.Stack;
import java.util.Vector;

/**
 * Created By liuyao on 2018/5/2 14:58.
 */
public class Dijkstra<Weight extends Number & Comparable> {

    private WeightedGraph G;           // 图的引用
    private int s;                     // 起始点
    private Number[] distTo;           // distTo[i]存储从起始点s到i的最短路径长度
    private boolean[] marked;          // 标记数组, 在算法运行过程中标记节点i是否被访问
    private Edge<Weight>[] from;       // from[i]记录最短路径中, 到达i点的边是哪一条,可以用来恢复整个最短路径

    // 构造函数, 使用Dijkstra算法求最短路径
    public Dijkstra(WeightedGraph g, int s) {
//        算法初始化
        G = g;
        this.s = s;
        distTo = new Number[G.V()];
        marked = new boolean[G.V()];
        from = new Edge[G.V()];
        for (int i = 0; i < G.V(); i++) {
            distTo[i] = 0.0;
            marked[i] = false;
            from[i] = null;
        }
//        使用索引堆记录当前找到的到达每个顶点的最短距离
        IndexMinHeap<Weight> ipq = new IndexMinHeap<>(G.V());

        distTo[s] = 0.0;
        from[s] = new Edge<Weight>(s, s, (Weight) (Number) 0.0);
        ipq.insert(s, (Weight) distTo[s]);
        marked[s] = true;
        while (!ipq.isEmpty()) {
//            当前索引堆中的最小堆的
            int v = ipq.extractMinIndex();
            marked[v] = true;

            // 对v的所有相邻节点进行更新
            for (Object item : G.adj(v)) {
                Edge<Weight> e = (Edge<Weight>) item;
                int w = e.other(v);

                // 如果从s点到w点的最短路径还没有找到
                if (!marked[w]) {

                    // 如果w点以前没有访问过,
                    // 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新
                    if (from[w] == null || distTo[v].doubleValue() + e.wt().doubleValue() < distTo[w].doubleValue()) {
//                        更新distTo[w]的值
                        distTo[w] = distTo[v].doubleValue() + e.wt().doubleValue();
                        from[w] = e;
                        if (ipq.contain(w)) {
                            ipq.change(w, (Weight) distTo[w]);
                        } else {
                            ipq.insert(w, (Weight) distTo[w]);
                        }
                    }
                }
            }
        }
    }

    // 返回从s点到w点的最短路径长度
    public Number shortestPathTo(int w) {
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);
        return distTo[w];
    }

    // 判断从s点到w点是否联通
    public boolean hasPathTo(int w) {
        assert w >= 0 && w < G.V();
        return marked[w];
    }

    // 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
    Vector<Edge<Weight>> shortestPath(int w) {
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);
        Stack<Edge<Weight>> s = new Stack<>();
        Edge<Weight> e = from[w];
//        从当前节点倒推回去并放入栈中
        while (e.v() != this.s) {
            s.push(e);
            e = from[e.v()];
        }
        s.push(e);
//        再从栈中取出元素,获得顺序从s到w中的路径
        Vector<Edge<Weight>> res = new Vector<>();
        while (!s.isEmpty()) {
            e = s.pop();
            res.add(e);
        }
        return res;
    }

    // 打印出从s点到w点的路径
    void showPath(int w) {
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);
        Vector<Edge<Weight>> path = shortestPath(w);
        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.elementAt(i).v() + " -> ");
            if (i == path.size() - 1) {
                System.out.println(path.elementAt(i).w());
            }
        }
    }

    // 测试我们的Dijkstra最短路径算法
    public static void main(String[] args) {

        String filename = "testG1-3.txt";
        int V = 5;

        SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
        // Dijkstra最短路径算法同样适用于有向图
        //SparseGraph<int> g = SparseGraph<int>(V, false);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        System.out.println("Test Dijkstra:\n");
        Dijkstra<Integer> dij = new Dijkstra<Integer>(g, 0);
        for (int i = 1; i < V; i++) {
            if (dij.hasPathTo(i)) {
                System.out.println("Shortest Path to " + i + " : " + dij.shortestPathTo(i));
                dij.showPath(i);
            } else {
                System.out.println("No Path to " + i);
            }

            System.out.println("----------");
        }

    }
}

2. Bellman-Ford 单源最短路径

Bellman-Ford算法的前提是:图中不能有负权环存在,但Bellman-Ford可以判断出图中是否有负权环的存在,算法的复杂度为O(EV)

如何判断是否存在负权环:

如果一个图中没有负权环,从一个点到另外一点的最短路径,最多经过所有的V个顶线,有V-1条边,否者存在顶点经过了两次,即存在负权环。

对一个点的一次松弛操作,就是找到经过这个点的另外一条路径,多一条边,权值更小。如果一个图没有负权环负权环,从一点到另外一点的最短路径,最多经过所有的V个顶线,有V-1条边,对所有的点进行V-1次松弛操作。对所有的点进行V-1次松弛操作,理论上就找到了从源点到其他所有点的最短路径,如果还可以继续松弛,原图中有负权环存在。

package com.liuyao.graph2.BellmanFord;

import com.liuyao.graph2.Edge;
import com.liuyao.graph2.ReadWeightedGraph;
import com.liuyao.graph2.SparseWeightedGraph;
import com.liuyao.graph2.WeightedGraph;

import java.util.Stack;
import java.util.Vector;

/**
 * Created By liuyao on 2018/5/2 17:24.
 */
public class BellmanFord<Weight extends Number & Comparable> {
    private WeightedGraph G; //图的引用
    private int s;
    private Number[] distTo;
    private Edge<Weight>[] from;
    private boolean hasNegativeCycle;

    // 构造函数, 使用BellmanFord算法求最短路径
    public BellmanFord(WeightedGraph g, int s) {
        G = g;
        this.s = s;
        distTo = new Number[G.V()];
        from = new Edge[G.V()];
        // 初始化所有的节点s都不可达, 由from数组来表示
        for (int i = 0; i < G.V(); i++) {
            from[i] = null;
        }

        // 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0
        distTo[s] = 0.0;
        from[s] = new Edge<Weight>(s, s, (Weight) (Number) 0.0);

        // Bellman-Ford的过程
        // 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离
        for (int pass = 1; pass < G.V(); pass++) {
            // 每次循环中对所有的边进行一遍松弛操作
            // 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边
            for (int i = 0; i < G.V(); i++) {
                // 使用我们实现的邻边迭代器遍历和所有顶点相邻的所有边
                for (Object item : G.adj(i)) {
                    // 对于每一个边首先判断e->v()可达
                    // 之后看如果e->w()以前没有到达过, 显然我们可以更新distTo[e->w()]
                    // 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离, 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()]
                    Edge<Weight> e = (Edge<Weight>) item;
                    if (from[e.v()] != null && (from[e.w()] == null || distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue())) {
                        distTo[e.w()] = distTo[e.v()].doubleValue() + e.wt().doubleValue();
                        from[e.w()] = e;
                    }
                }
            }
        }
        hasNegativeCycle = detectNegativeCycle();

    }

    // 判断图中是否有负权环
    private boolean detectNegativeCycle() {
        for (int i = 0; i < G.V(); i++) {
            for (Object item : G.adj(i)) {
                Edge<Weight> e = (Edge<Weight>) item;
                if (from[e.v()] != null && distTo[e.v()].doubleValue() + e.wt().doubleValue() < distTo[e.w()].doubleValue()) {
                    return true;
                }
            }
        }
        return false;
    }

    // 返回图中是否有负权环
    public boolean negativeCycle() {
        return hasNegativeCycle;
    }

    // 返回从s点到w点的最短路径长度
    public Number shortestPathTo(int w) {
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);
        return distTo[w];
    }

    // 判断从s点到w点是否联通
    public boolean hasPathTo(int w) {
        assert w >= 0 && w < G.V();
        return from[w] != null;
    }

    // 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
    Vector<Edge<Weight>> shortestPath(int w) {
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);
        Stack<Edge<Weight>> s = new Stack<>();
        Edge<Weight> e = from[w];
//        从当前节点倒推回去并放入栈中
        while (e.v() != this.s) {
            s.push(e);
            e = from[e.v()];
        }
        s.push(e);
//        再从栈中取出元素,获得顺序从s到w中的路径
        Vector<Edge<Weight>> res = new Vector<>();
        while (!s.isEmpty()) {
            e = s.pop();
            res.add(e);
        }
        return res;
    }

    // 打印出从s点到w点的路径
    void showPath(int w) {
        assert w >= 0 && w < G.V();
        assert hasPathTo(w);
        Vector<Edge<Weight>> path = shortestPath(w);
        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.elementAt(i).v() + " -> ");
            if (i == path.size() - 1) {
                System.out.println(path.elementAt(i).w());
            }
        }
    }

    // 测试我们的Bellman-Ford最短路径算法
    public static void main(String[] args) {

        String filename = "testG1-4.txt";
//        String filename = "testG_negative_circle.txt";
        int V = 5;

        SparseWeightedGraph<Integer> g = new SparseWeightedGraph<Integer>(V, true);
        ReadWeightedGraph readGraph = new ReadWeightedGraph(g, filename);

        System.out.println("Test Bellman-Ford:\n");

        int s = 0;
        BellmanFord<Integer> bellmanFord = new BellmanFord<Integer>(g, s);
        if (bellmanFord.negativeCycle()) {
            System.out.println("The graph contain negative cycle!");
        } else {
            for (int i = 0; i < V; i++) {
                if (i == s) {
                    continue;
                }

                if (bellmanFord.hasPathTo(i)) {
                    System.out.println("Shortest Path to " + i + " : " + bellmanFord.shortestPathTo(i));
                    bellmanFord.showPath(i);
                } else {
                    System.out.println("No Path to " + i);
                }

                System.out.println("----------");
            }
        }

    }

}

  • 9 min read

CONTRIBUTORS


  • 9 min read