天天看點

最短路徑問題

最短路徑問題

本文将解析如何使用 Dijkstra 算法求解最短路徑問題

如下圖:

最短路徑問題

就像上圖, 每一個點可以了解成一個岔路口, 線段就是路徑, 線段上的值為長度, 如何找到從 v0到各個岔路口的最小值, 也就是最短路徑問題

  • **如何使用代碼表示出上圖呢? **

最短路徑問題 和 深度廣度搜尋一樣, 都是建立在圖這個資料結構上的, 是以我們可以選用鄰接表 或者是臨接矩陣 來表示上圖 , 封裝類如下:

public class Graph01 {

    // 使用鄰接表的方式表示圖
    private LinkedList<Edge> [] graph ;
    // 圖中一共多少個點
    private int size;

    public Graph01(int size) {
        this.size = size;
        this.graph = new LinkedList[this.size];
        for (int i = 0; i < size; i++) {
            graph[i]=new LinkedList<>();
        }
    }

    // 添加點的方法
    public void addEdge(int s, int e, int w) {
        this.graph[s].add(new Edge(s, e, w));
    }      

它大概長這個樣子:

最短路徑問題
  • 如何表示兩點之間的邊?

一條邊有三個描述屬性, 兩邊的頂點 + 權重

// 邊的封裝類
    private class Edge {
        // 開始點的值
        private int start;
        // 結束點的值
        private int end;
        // 權重
        private int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }      
  • 如何表示頂點

使用兩個屬性描述頂點, 分别是 dist 和 id , 比如我們描述 v3 , 那麼它的id = 3 , dist是到起點v0的距離, 故 dist =13

// 圖中各個點的封裝類
    private class Vertex implements Comparable<Vertex> {
        // 使用者指定的起點到目前點的距離
        private int dist;
        // 頂點的id (v1 v2 中的 1 和 2)
        private int id;

        public Vertex(int dist, int startId) {
            this.dist = dist;
            this.id = startId;
        }

        @Override
        public int compareTo(Vertex o) {
            if (o.dist > this.dist) return -1;
            else return 1;
        }
    }      
  • 尋找最短路徑的思路
最短路徑問題

還是看這個圖: 比如我們尋找的最短路徑就是 v0 到 其它所有的頂點的最短路徑 , 按照廣度優先順序周遊這個圖

尋找 v0 的臨接點 , 于是我們能發現 v1 v2 v4 v6 這四個點都是v0的臨界點, 然後我們分别給 v1 v2 v4 v6 這四個點做出如下的标記

v1.dist = 13   // dist表示的是 目前點到起點的距離
 v2.dist = 8
 v4.dist = 30
 v6.dist = 32      

但是我們發現, 直接相連 , 并不一定是最短的 , 就像下面這樣 , 雖然都能到v4 , 但是很顯然, 如果按照​

​v0 -> v2 -> v3 -> v4​

​ 會更近 , 這就意味着我們需要不斷的更新每一個節點到起點的dist值

v0.dist + v4.dist = 30
 v0.dist + v2.dist + v3.dist = 19      

那麼, 是否存在一個點到起點v0的dist是 百分百确定并且不會更改呢??? 沒錯,就是 它所有臨界點中, dist最小的那個點

于是, 我們的編碼流程就是下面這樣

  1. 找到起點
  2. 将起點添加進隊列(因為我們是廣度優先周遊)
  3. 循環周遊隊列中的值
  1. 如果目前點 == 結束點 , 就 break
  2. 從隊列中取出dist 最小的點 記作 目前點
  3. 找到目前點的所有直接 臨接點
  4. 挨個周遊根節點的臨界點
  1. 如何未被通路過, 并且 目前點.dist + 目前路徑的長度 < 目前點的下一個點的dist (說明找到了比原來标記的最短路徑 , 更短的路徑) , 然後 用前者更新後者的值
  2. 将目前點加入到可以還原路徑長度的輔助數組中
  3. 如果目前點的下一個點未被通路過, 标記它被通路了, 然後加入隊列中
預設所有的點的 dist = Integer.MAXVALUE

如果看這圖, 用筆跟着上面的邏輯畫一下的話, 就能發現, 确實能找到 v0到其他各個點的最短路徑, 唯一不好了解的部分就是我們用黑色加粗的地方,

最短路徑問題

我們舉例子解釋一下 , 還是上圖:

**比如, 就從開頭說 : **

通過上面的步驟4 , 我們可以周遊到v0的直接臨接點是 v4 , 這是第一次通路, 于是我們可以繼續處理, 然後我們按照 步驟4.1 進行判斷 ​

​v0.dist + 30 < v4.dist​

​​ 條件滿足了(預設所有的點的 dist = Integer.MAXVALUE), 于是我們就更新 ​

​v4.dist = v0.dist + 30 < v4.dist =30 ​

經過了幾輪循環後, 假設目前已經是v3了, 這是我們繼續來到步驟4.1中進行判斷, ​

​v3.dist + 6 < v4.dist​

​​ 我們發現也是滿足的, 因為一開始算出了 v4.dist= 30 , 于是進一步更新這個值, 使​

​ v4.dist = v3.dist + 6​

​ , 這樣疊代下面 , 我們就能擷取到起點 到所有點的最短路徑

public void dijkstra(int start, int end) {
        // 标記是否曾通路過
        boolean[] visited = new boolean[this.size];
        // 還路徑
        int [] resultArray = new int[this.size];
        // 存放圖中的所有的頂點
        Vertex[] vertices = new Vertex[this.size];
        for (int i = 0; i < vertices.length; i++) {
            vertices[i]=new Vertex(Integer.MAX_VALUE,i);
        }

        // 擷取頂點, 并賦初值為0
        Vertex startVertex = vertices[0];
        startVertex.dist = 0;
        visited[start] = true;
        // 建立隊列,并将頭結點入隊
        Queue<Vertex> queue = new PriorityQueue<>();
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            // 取出目前距離開始點 dist 最近的點
            Vertex minVertex = queue.poll();
            // 如果已經找到了頂點就退出去
            if (minVertex.id==end) break;

            // 周遊目前點的所有臨接點
            for (int i = 0; i < graph[minVertex.id].size(); i++) {
                // 依次擷取出他們的邊
                Edge edge = graph[minVertex.id].get(i);
                // 根據邊的資訊, 取出它的取出它的臨界點
                Vertex nextVertex = vertices[edge.end];

                // 如果目前點 + 目前邊的長度 < 目前點到它臨界點nextVertex的長度 就說明找到了這個直連點更新的點路徑, 于是更新原來的直聯點的資料
                if (minVertex.dist + edge.weight < nextVertex.dist) {
                    // 更新原來的不準确的路徑值
                    nextVertex.dist = minVertex.dist + edge.weight;

                    /**
                     * 數值  0 0 0 2 0 0 0
                     * 下标  0 1 2 3 4 5 6
                     *
                     * 下标為3位置的值為2 , 表示在圖中  vertex3的前面的vertex2
                     */
                    resultArray[nextVertex.id]=minVertex.id;
                    if (!visited[nextVertex.id]){
                        queue.add(nextVertex);
                        visited[nextVertex.id]=true;
                    }
                }
            }
        }
        System.out.print(start);
        print( start,end ,resultArray);
    } 
   /**
     * 例如:
     * 數值:  0 0 0 2 3 1 1
     * 下标:  0 1 2 3 4 5 6
     *  我們得到 從 0 - 6 的路徑該怎麼走呢? 按照如下的順序将方法壓入棧, 彈棧時即可擷取到路徑
     * 
     *  | 0 0 |
     *  | 0 1 |
     *  | 0 6 |   方法棧
     * ----------
     */
    private void print(int start, int end, int[] resultArray) {
        if (start==end) return;
        print(start,resultArray[end],resultArray);
        System.out.print("->"+end);
    }