美文网首页算法
14.最短路径

14.最短路径

作者: 哈哈大圣 | 来源:发表于2019-10-20 23:33 被阅读0次

    最短路径Short Path

    点击这里,前提知晓...

    一、相关概念

    最短路径是针对于有权图进行分析

    1). 常见应用场景


    最短路径的应用.png

    本次讨论是单源最短路径(Single Source Shortest Path),可以一个带权图中一个点到图中任意一个点的最短路径。

    2).【松弛操作】


    松弛操作.png

    如上图所示,从节点0到节点1,节点0的一个邻边就是节点1,但是可以经过邻边节点2再到节点1,这种通过折中的方式到达邻边就是松弛操作。松弛操作是最短路径的求解核心

    二、Dijkstra单元最短路径算法

    1). 算法前提以及特点

    1. 所求图中不能有负权边
    2. 算法复杂度为O(Elog(V)); E为边数,V为点数

    2). 算法思想

    以一个图例说明算法的思想


    Dijkstra单源最短路径算法示例.png

    如图,起始点为点0,进行初始化,遍历点0的所有邻边,此时从点0到点1的距离为5 (后续的举例都以点0为参考点),到点2的距离为2,到点3的距离为6 (将这些值放入索引堆中),由于图中不存在负权边,所以点0到点2最短路径就是2,因为,如果进行松弛操作,发现到点1,点3的距离已经大于2了,由于没有负权边,所以距离不可能大于2;此时再从索引堆中弹出最小的,也就是点2,然后遍历节点2所有没有被标记找到最短路径的节点,此时发现到点1的距离为3,覆盖之前的记录,到点4的距离为7,到点3的距离5,小于之前的6,覆盖掉;按照之前的逻辑,目前邻边最短的就是到点1,距离为3,因为从点4,和点3再中转到点1就不可能小于3了,将点1弹出,然后遍历点1所有没有被标记找到最短路径的节点,只有点4,此时距离点4为4,而且在堆中已经最小,所以点4的最短路径确定,弹出;最后只有点3,访问点3的所有邻边,同样的逻辑,发现已有的距离5最小,则点3确定。

    3). 代码实现

    1. 辅助数据结构IndexMinHeap、Edge参考文章头链接

    2. Dijkstra

    import java.util.Iterator;
    import java.util.Stack;
    import java.util.Vector;
    
    /**
     * @author Liucheng
     * @since 2019-10-20
     */
    public class Dijkstra<Weight extends Number & Comparable> {
    
        private WeightedGraph G;           // 图的引用
        private int s;                     // 起始点
        private Number[] distTo;           // distTo[i]存储从起始点s到i的最短路径长度
        private IndexMinHeap<Weight> heap; // 寻找最短权值的最小索引堆。
        private boolean[] marked;          // 标记数组, 在算法运行过程中标记节点i是否被访问
        private Edge<Weight>[] from;       // from[i]记录最短路径中, 到达i点的边是哪一条,可以用来恢复整个最短路径
    
    
        // 构造函数
        public Dijkstra(WeightedGraph graph, int s) {
            this.G = graph;
            this.s = s;
            this.distTo = new Number[graph.V()];
            this.heap = new IndexMinHeap<>(graph.V());
            this.marked = new boolean[graph.V()];
            this.from = new Edge[graph.V()];
    
            this.shortestRoad();
        }
    
        // 使用Dijkstra算法计算最短路径
        private void shortestRoad() {
    
            // 对起始点s进行初始化,【s -> s】 点为对应的最短路径
            this.distTo[s] = 0.0;
            this.from[s] = new Edge<>(s, s, (Weight) this.distTo[s]);
            this.heap.insert(s, (Weight) this.distTo[s]);
            this.marked[s] = true;
    
            // 执行Dihkstra算法
            while (!heap.isEmpty()) {
                // 取出堆中的最小值,最小值对应节点就是被找到对应最短路径的点
                int v = heap.extractMinIndex();
                // 从前面的循环中,v点对应的边已经添加到了from数组中,此处标记为true,就确定了s点到v点的最短路径!
                marked[v] = true;
    
                // 对v的所有相邻节点进行更新
                Iterator iterator = this.G.adj(v).iterator();
                while (iterator.hasNext()) {
                    Edge<Weight> e = (Edge<Weight>)iterator.next();
                    // 当前访问点的边的另一点
                    int w = e.other(v);
    
                    // 如果从s点到w点的最短路径还没有找到
                    if (!marked[w]) {
    
                        // distTo[v]就是s到v的最短距离
                        Number curDis = distTo[v].doubleValue() + e.wt().doubleValue();
                        /* 如果记录最短距离数组中对应的值为空,表示还没有访问到此点;
                           如果存在,则判断新的路径是否比原来找到的更短*/
                        if (distTo[w] == null || curDis.doubleValue() < distTo[w].doubleValue()) {
                            // 更新最短的值
                            distTo[w] = curDis;
    
                            /* 记录当前到达w点的上一节点e,
                               后续执行可能被更短的路径方式覆盖,也有可能此方式就为最短路径*/
                            from[w] = e;
    
                            if (heap.contain(w)) {
                                heap.change(w, (Weight)curDis);
                            } else {
                                // 对应distTo[w] == null的情况
                                heap.insert(w, (Weight)curDis);
                            }
                        }
                    }
                }
            }
        }
    
        // 返回从s点到w点的最短路径的长度
        public Number shortestPathTo(int w) {
            return distTo[w];
        }
    
        // 判断从s点到w点是否联通
        private boolean hasPathTo(int w) {
            return marked[w];
        }
    
        // 寻找从s到w的最短路径,将整个路径经过的边存放在vec中
        private Vector<Edge<Weight>> shortestPath(int w) {
            assert this.hasPathTo(w);
    
            // 通过from数组逆向查找放在栈中
            Stack<Edge<Weight>> stack = new Stack<>();
            Edge<Weight> weightEdge = this.from[w];
            while (weightEdge.v() != this.s) {
                stack.push(weightEdge);
                weightEdge = from[weightEdge.v()];
            }
    
            stack.push(weightEdge);
    
            Vector<Edge<Weight>> vec = new Vector<>(stack.size());
            while (!stack.empty()) {
                vec.add(stack.pop());
            }
    
            return vec;
        }
    
        // 打印出从s点到w点的路径
        public 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());
            }
        }
    
    
        public static void main(String[] args) {
            String filename = Thread.currentThread().getContextClassLoader().getResource("testG1.txt").getPath();
            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("----------");
            }
        }
    }
    
    1. 测试文件testG1.txt
    5 8
    0 1 5
    0 2 2
    0 3 6
    1 4 1
    2 1 1
    2 4 5
    2 3 3
    3 4 2
    
    1. 测试结果
    /*
    Test Dijkstra:
    
    Shortest Path to 1 : 3.0
    0 -> 2 -> 1
    ----------
    Shortest Path to 2 : 2.0
    0 -> 2
    ----------
    Shortest Path to 3 : 5.0
    0 -> 2 -> 3
    ----------
    Shortest Path to 4 : 4.0
    0 -> 2 -> 1 -> 4
    ----------
     */
    

    三、负权边 Bellman-Ford单源最短路径算法

    1). 算法思想以及注意事项

    1. 不能存在负权环:在一个负权环中持续计算,就没有最短路径了(比如从点1到点2再到点3权值和为-1,每次转一圈就减1)
    2. 虽然图中有负权边则无法计算出最短路径,但是可以检测是否有负权环;
    3. 复杂度O(EV)
    4. 从一点到另外一点的最短路径,最多经过所有的V个顶点,有V-1条边,如果可以经过V及其以上的边,那么图中就一定存在负权环。

    算法思想: 利用上述4点的特性,假设最坏的情况就是到每个边的最短路径有(v-1)条边 (不可能成立),可以对所有的点都进行(v-1)次松弛操作,必然可以找到从原点到该点的最短路径!如果再对每个点进行松弛操作还发现有更短的边,则此图中必有负权边!

    2). 代码实现

    import java.util.Iterator;
    import java.util.Stack;
    import java.util.Vector;
    
    /**
     * 使用BellmanFord算法求最短路径
     * @author Liucheng
     * @since 2019-10-20
     */
    public class BellmanFord<Weight extends Number & Comparable> {
    
        private WeightedGraph G;  // 图的引用
        private int s;            // 起始点
        private Number[] distTo;  // distTo[i]存储从起始点s到i的最短路径长度
        Edge<Weight>[] from;      // from[i]记录最短路径中, 到达i点的边是哪一条,可以用来恢复整个最短路径
        boolean hasNegativeCycle; // 标记图中是否有负权环
    
        // 构造函数
        public BellmanFord(WeightedGraph graph, int s) {
            // 初始化
            this.G = graph;
            this.s = s;
            this.distTo = new Number[G.V()];
            this.from = new Edge[G.V()];
    
            this.shortestRoad();
        }
    
        // 使用BellmanFord算法求最短路径
        private void shortestRoad() {
            /*设置distTo[s] = 0,并且让from[s]不为null,
            表示初始节点科大且距离为0*/
            distTo[s] = 0.0;
            from[s] = new Edge<>(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++) {
                    // 使用迭代器遍历和所有顶点相邻的所有边
                    Iterator iterator = G.adj(i).iterator();
                    while (iterator.hasNext()) {
                        Edge<Weight> e = (Edge<Weight>)iterator.next();
    
                        /*对于每一个边首先判断e.v()可达
                        之后看如果e.w()以前没有到达过,显然我们可以更新distTo[e.w()]
                        或者e.w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离,
                        即可以进行一次松弛操作, 我们也可以更新distTo[e.w()]*/
                        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;
                        }
                    }
                }
            }
            this.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 !hasNegativeCycle;
            assert hasPathTo(w);
            return distTo[w];
        }
    
        // 判断从s点到w点是否联通
        private boolean hasPathTo(int w) {
            return from[w] != null;
        }
    
        // 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中
        private Vector<Edge<Weight>> shortestPath(int w){
    
            assert w >= 0 && w < G.V() ;
            assert !hasNegativeCycle ;
            assert hasPathTo(w) ;
    
            // 通过from数组逆向查找到从s到w的路径, 存放到栈中
            Stack<Edge<Weight>> s = new Stack<Edge<Weight>>();
            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<Edge<Weight>>();
            while( !s.empty() ){
                e = s.pop();
                res.add(e);
            }
            return res;
        }
    
        // 打印出从s点到w点的路径
        public void showPath(int w){
            assert(w >= 0 && w < G.V());
            assert(!hasNegativeCycle);
            assert(hasPathTo(w));
    
            Vector<Edge<Weight>> res = shortestPath(w);
            for( int i = 0 ; i < res.size() ; i ++ ){
                System.out.print(res.elementAt(i).v() + " -> ");
                if( i == res.size()-1 )
                    System.out.println(res.elementAt(i).w());
            }
        }
    
    }
    

    四、总结

    1. Bellman-Ford算法的优化:利用队列数据结构queue-based bellman-ford算法

    2. 单源最短路径算法


    单源最短路径算法.png

    确定起始点,到任意其他点

    1. 所有对最短路径算法
      • Folyed算法,处理无负权环的图,O(V^3)

    任意两点的最短路径

    1. 最长路径算法

    最长路径算法.png

    相关文章

      网友评论

        本文标题:14.最短路径

        本文链接:https://www.haomeiwen.com/subject/ggkzmctx.html