最短路徑

問題

對于如下的圖來說，每一個“ ∙ ”代表一個節點，節點與節點之間是他們之間相應的邊權，由于這個圖類似于矩陣的形式，是以當給定坐标 (x1,y1)和(x2,y2) 時，求這兩個節點之間的最短路徑。
在下面這個圖中，最原始的圖應該是每條邊代表轉移機率，這裡将機率乘以10取整後得到，也就是每個節點相連邊的權值和為10.

∙−5−∙−4−∙−4−∙−5−∙|||||51215|||||∙−3−∙−3−∙−3−∙−1−∙|||||23254|||||∙−1−∙−1−∙−1−∙−1−∙|||||75635|||||∙−3−∙−2−∙−2−∙−5−∙

如何有效存儲圖？

最通常存儲圖的方式主要有兩種，一種是鄰接矩陣，鄰接矩陣比較直覺易懂，但是通常來說非常消耗空間；另一種是鄰接表。
如果矩陣是 m∗n 階的話，橫向的邊數為 m∗(n−1) ，縱向的邊數為 (m−1)∗n ，是以總共的邊數為 m∗(n−1)+(m−1)∗n=2mn−m−n ，是以在這裡至少需要 O(2mn−m−n)=O(mn) 的存儲空間，如果使用鄰接矩陣的形式存儲的話則需要 O(mn∗mn)=O(m2∗n2) 的存儲空間，但是這裡的每個節點最多與4個節點相鄰，也就是最多與4條邊相連，是以鄰接矩陣的空間消耗是非常大的。
- 這裡使用兩種方式存儲這種圖。
- 用兩個矩陣分别存儲水準方向的邊和垂直方向的邊，分别命名為rows和cols，并且為了避免重複，在水準方向上的邊隻存儲每個節點往右的邊，在垂直方向上隻存儲每個節點往下的邊。這樣，最後一列和最後一行實際上是不需要存儲的，但是為了友善起見，存儲0也無妨。是以上述的圖有
```
rows = 
        5 4 4 5 0
        3 3 3 1 0
        1 1 1 1 0
        3 2 2 5 0     

cols = 
        5 1 2 1 5
        2 3 2 5 4
        5 1 2 1 5
        0 0 0 0 0
           
```
- 另外一種存儲方式為：将圖看做一個有向圖，将向右和向下的邊當做出邊，針對每個節點隻存該節點的出邊，于是有如下存儲方式：
```
nodes = 
        5 5
        4 1
        4 2
        5 1
        0 5
        ...
        0 0
           
```

求解最短路徑

因為每條邊權值都為正，是以用Dijkstra算法求解。基本思路是，從起始點出發，不斷尋找目前能找到的離起始點最短路徑的節點，然後以該節點作為中間節點，考察是否可以更新以該節點為中間節點的其他節點的距離。是一種層層遞進的思路，直到到達所求的節點。基于這種思路，有以下解法：

Solution1

public int getMinPath1(int[][] rows, int[][] cols, int x1, int y1, int x2, int y2){//求(x1, y1)和(x2, y2)之間的最短路徑
    int m = rows.length;
    if(m==) return -;
    int n = rows[].length;
    if(n==||x1>m||x2>m||x1<||x2<||y1>n||y2>n||y1<||y2<) return -;//這些都是非法情況
    boolean[][] done = new boolean[m][n];//記錄該節點是否已經找到最短路徑了
    int[][] distance = new int[m][n];//記錄從起始點到該節點的目前最短路徑
    for(int i=;i<m;i++) Arrays.fill(distance[i],Integer.MAX_VALUE);
    distance[x1][y1] = ;//起始點的最短路徑為0
    int x=, y=,min = Integer.MAX_VALUE;
    for(int k=;k<m*n;k++,min = Integer.MAX_VALUE){ //總共有m*n個節點，最壞情況下要循環m*n次
        for(int i=;i<m;i++){       //找到還未考察過的節點中的最短路徑
            for(int j=;j<n;j++){
                if(!done[i][j]&&distance[i][j]<min){
                    x = i;
                    y = j;
                    min = distance[i][j];
                }
            }
        }
        if(x == x2 && y == y2) return distance[x2][y2];//已經找到所求節點的最短路徑了，直接退出
        done[x][y] = true;
        if(x > ) distance[x-][y] = Math.min(distance[x-][y], distance[x][y] + cols[x-][y]);//往上走
        if(x < m-) distance[x+][y] = Math.min(distance[x+][y], distance[x][y] + cols[x][y]);//往下走
        if(y > ) distance[x][y-] = Math.min(distance[x][y-], distance[x][y] + rows[x][y-]);//往左走
        if(y < n-) distance[x][y+] = Math.min(distance[x][y+], distance[x][y] + rows[x][y]);//往右走
    }
    return distance[m-][n-];
}

調試結果如下：

最短路徑最短路徑
```
最下方的矩陣為最終生成的到每個節點的最短路徑
           
```
- 如果矩陣 m∗n 階，因為有 N=m∗n 個節點，是以這種解法的空間複雜度為 O(N) ；求解最短路徑過程中，最外層for循環最壞情況下要對所有節點都周遊一次，是以是 O(N) ，裡層的for循環在尋找目前最短路徑的時候周遊了所有節點，時間複雜度也是 O(N) ，是以總的時間複雜度為 O(N2) 。

Solution2

如果用另一種圖的存儲方式來求解的話，但是時間和空間複雜度與Solution1一樣。代碼如下：

public int getMinPath2(int[][] rows, int[][] cols, int x1, int y1, int x2, int y2){
    int m = rows.length;
    if(m==) return -;
    int n = rows[].length;
    if(n==||x1>m||x2>m||x1<||x2<||y1>n||y2>n||y1<||y2<) return -;
    int[][] nodes = new int[m*n][];//有兩列，第一列為每個節點往右的邊，第二列為往下的邊
    for(int i=;i<m;i++){//這裡是将圖的存儲方式換成節點清單的形式
        for(int j=;j<n;j++){
            nodes[n*i+j][] = rows[i][j];
            nodes[n*i+j][] = cols[i][j];
        }
    }
    boolean[] done = new boolean[m*n];
    int[] distance = new int[m*n];
    Arrays.fill(distance,Integer.MAX_VALUE);
    distance[x1*n+y1] = ;
    int x=, min = Integer.MAX_VALUE;
    for(int k=;k<m*n;k++,min = Integer.MAX_VALUE){ //總共有m*n個節點，最壞情況下要循環m*n次
        for(int i=;i<m*n;i++){       //找到還未考察過的節點中的最短路徑
            if(!done[i]&&distance[i]<min){
                x = i;
                min = distance[i];
            }
        }
        if(x == x2*n + y2) return distance[x];//已經找到最短路徑了，直接退出
        done[x] = true;
        if(x/n > ) distance[x-n] = Math.min(distance[x-n], distance[x] + nodes[x-n][]);
        if(x/n < m-) distance[x+n] = Math.min(distance[x+n], distance[x] + nodes[x][]);
        if(x%n > ) distance[x-] = Math.min(distance[x-], distance[x] + nodes[x-][]);
        if(x%n < n-) distance[x+] = Math.min(distance[x+], distance[x] + nodes[x][]);
    }
    return distance[m*n-];
}

調試結果如：

最短路徑最短路徑

Solution3

針對上述解法，最外層循環因為是要對所有節點進行周遊去考察最短路徑，是以在這裡無法進行優化，主要針對内層每次尋找目前最短路徑節點的方法進行優化，由于每一次都是要得到最短路徑，是以可以選擇用最小堆（優先隊列）來儲存目前節點，而最小堆的插入和删除都是 O(N) 的複雜度，是以可以将程式的時間複雜度優化到 O(NlogN) 。代碼如下：

public int getMinPath3(int[][] rows, int[][] cols, int x1, int y1, int x2, int y2){
    int m = rows.length;
    if(m==) return -;
    int n = rows[].length;
    if(n==||x1>m||x2>m||x1<||x2<||y1>n||y2>n||y1<||y2<) return -;
    boolean[][] done = new boolean[m][n];
    int[][] distance = new int[m][n];
    for(int i=;i<m;i++) Arrays.fill(distance[i],Integer.MAX_VALUE);
    distance[x1][y1] = ;
    int x=, y=;
    PriorityQueue<Node> pq = new PriorityQueue<Node>(,new Comparator<Node>(){
        public int compare(Node n1, Node n2){
            return n1.val - n2.val;
        }
    });//這裡定義了一個最小堆，使用node的val進行排序。因為加入最小堆的時候，除了帶有路徑值外還必須有節點的位置資訊。是以這裡定義了一個node類。詳細見下面
    pq.add(new Node(,x1,y1));
    while(pq.size()>){//最壞情況下，一個節點會重複添加進去4次，是以這裡O(4N)=O(N)
        Node node = pq.poll();//最小堆的添加和删除操作都是O(logN)
        x = node.x;
        y = node.y;
        if(done[x][y]) continue;//在這裡需要done數組的原因在于一個節點的不同距離都存入了最小堆中，目前節點已經找到過最小距離時直接跳過
        //實際上，可以如此：if(distance[x][y]!=node.val) continue;這同樣可以避免重複考察一個已經找到最短路徑的節點，并且節省了done數組的空間
        if(x == x2 && y == y2) return distance[x2][y2];//已經找到最短路徑了，直接退出
        done[x][y] = true;
        if(x > &&distance[x-][y]>distance[x][y] + cols[x-][y]){
            distance[x-][y] = distance[x][y] + cols[x-][y];
            pq.add(new Node(distance[x-][y],x-,y));
        }
        if(x < m-&&distance[x+][y]>distance[x][y] + cols[x][y]){
            distance[x+][y] = distance[x][y] + cols[x][y];
            pq.add(new Node(distance[x+][y],x+,y));
        }
        if(y > &&distance[x][y-]>distance[x][y] + rows[x][y-]){
            distance[x][y-] = distance[x][y] + rows[x][y-];
            pq.add(new Node(distance[x][y-],x,y-));
        }
        if(y < n-&&distance[x][y+]>distance[x][y] + rows[x][y]){
            distance[x][y+] = distance[x][y] + rows[x][y];
            pq.add(new Node(distance[x][y+],x,y+));
        }
    }
    return distance[m-][n-];
}

下面是程式中用到的類Node：

class Node{
int val = ;//該節點的目前最短路徑
int x = ;//節點坐标
int y = ;
Node(int val, int x, int y){this.val = val; this.x = x; this.y = y;}
Node(){}
}

調試結果如圖：

最短路徑最短路徑

圖中是從矩陣左上角到右下角的最短路徑，下方的矩陣為最終生成的到每個節點的最短路徑。

Solution4

如果使用第二種存儲方式，依然利用優先隊列的方式來求解的話則有：

public int getMinPath4(int[][] rows, int[][] cols, int x1, int y1, int x2, int y2){
    int m = rows.length;
    if(m==) return -;
    int n = rows[].length;
    if(n==||x1>m||x2>m||x1<||x2<||y1>n||y2>n||y1<||y2<) return -; 

    int[][] nodes = new int[m*n][];
    for(int i=;i<m;i++){
        for(int j=;j<n;j++){
            nodes[n*i+j][] = rows[i][j];
            nodes[n*i+j][] = cols[i][j];
        }
    }
    boolean[] done = new boolean[m*n];
    int[] distance = new int[m*n];
    Arrays.fill(distance,Integer.MAX_VALUE);
    distance[x1*n+y1] = ;
    int x=;

    PriorityQueue<Node> pq = new PriorityQueue<Node>(,new Comparator<Node>(){
        public int compare(Node n1, Node n2){
            return n1.val - n2.val;
        }
    }); 

    pq.add(new Node(,x1*n+y1,-));//初始狀态加入最小堆
    while(pq.size()>){ //總共有m*n個節點，最壞情況下要循環m*n次
        Node node = pq.poll();
        x = node.x;
        if(node.val!=distance[x]) continue;
        if(x == x2*n + y2) return distance[x];//已經找到最短路徑了，直接退出
        done[x] = true;
        if(x/n > &&distance[x-n]>distance[x] + nodes[x-n][]){
            distance[x-n] = distance[x] + nodes[x-n][];
            pq.add(new Node(distance[x-n],x-n,-));
        }
        if(x/n < m-&&distance[x+n]>distance[x] + nodes[x][]){
            distance[x+n] = distance[x] + nodes[x][];
            pq.add(new Node(distance[x+n],x+n,-));
        }
        if(x%n > &&distance[x-]>distance[x] + nodes[x-][]){
            distance[x-] = distance[x] + nodes[x-][];
            pq.add(new Node(distance[x-],x-,-));
        }
        if(x%n < n-&&distance[x+]>distance[x] + nodes[x][]){
            distance[x+] = distance[x] + nodes[x][];
            pq.add(new Node(distance[x+],x+,-));
        }
    }
    return distance[m*n-];
}

調試結果如：

最短路徑最短路徑
這裡将最短路徑的矩陣用一維數組表示。

維特比算法

如果将矩陣中的每個位置當做一個狀态，并且将依次能找到的最短路徑當做時間t，則可以如下表示：
1. 初始狀态,時刻 t=0 ： δt(i)={Integer.MAX_VALUE,0,如果x不是起始點如果x是起始點
2. 對于時刻 t≥1 有：
  
  δt(i)=min1≤j≤N[δt−1(j)+aji],i=1,2,...,N;t=1,2,...
3. 循環第二步，直到時刻t找到的最短路徑為所求節點，終止算法運作。
對于算法中的第二步，要求狀态j到i的轉移，通常來說是要針對所有其他節點到狀态i的轉移，也就是 min1≤j≤N ，但是在這裡實際隻需要針對每個狀态i求最多的5個狀态，包括每個節點周邊的最多4個的鄰節點和一個自身節點。
根據上述思路實作的代碼和上面的Dijkstra算法是一樣的。

附錄：

以下是測試代碼，基本思路是針對每一組測試的(m,n)随機産生一個符合各節點邊權值和為10的測試用例，有些情況下比如(3,3)是不可能産生符合這個條件的測試用例的，是以在嘗試1000次還未能産生一個符合條件的用例情況下，跳過這個(m,n)對：

public static void main(String[] args){
    int[][] testCases = {{,},{,},{,},{,},{,},{,},{,},{,},{,},{,}};//每一對都是一組(m,n)
    Solution sl = new Solution();
    for(int[] arr:testCases){
        int m = arr[];
        int n = arr[];
        int[][] rows = new int[m][n];
        int[][] cols = new int[m][n];
        boolean flag = false;
        for(int k=;k<;k++){//針對每組(m,n)嘗試最多嘗試1000次直到有符合條件的用例
            flag = false;
            for(int i=;i<m;i++){
                for(int j=;j<n;j++){
                    if(i==&&j==){
                        rows[i][j] = (int) (Math.random() * ) + ;
                        cols[i][j] =  - rows[i][j];
                        continue;
                    }
                    int range =  - ( j> ? rows[i][j-] :  ) - ( i> ? cols[i-][j] :  );
                    if( i < m- ) {
                        if( j < n- ) rows[i][j] = (int) (Math.random() * (range-)) + ;//随機産生[1,10)
                    }else rows[i][j] = range;
                    cols[i][j] = range - rows[i][j]; 
                    if((j<n-?(rows[i][j]<=):false)||(i<m-?(cols[i][j]<=):false)){
                        flag = false;
                        break;
                    } 
                    flag = true;
                }
                if(!flag) break;//跳出多層循環
            }
            if(flag) break;
        }
        for(int i=;flag&&i<m;i++){//将測試用例列印出來
            for(int j=;j<n;j++) System.out.print("*" + (j<n-?(" -"+rows[i][j]+"- "):"\n"));
            for(int j=;i<m-&&j<n;j++) System.out.print("|" + (j<n- ? ("     "):"\n"));
            for(int j=;i<m-&&j<n;j++) System.out.print(cols[i][j] + (j<n- ? ("     "):"\n"));
            for(int j=;i<m-&&j<n;j++) System.out.print("|" + (j<n- ? ("     "):"\n"));
        }
        if(flag){
            //int x1= (int)(Math.random()*m),y1= (int)(Math.random()*n),x2= (int)(Math.random()*m),y2= (int)(Math.random()*n);//可以随機産生起始點和終止點
            int x1=, y1=, x2=m-, y2=n-;
            System.out.println("x1="+x1+", y1="+y1+";  x2= "+x2+",y2= "+y2);
            /*int[][] result = sl.getMinPath1(rows,cols,x1,y1,x2,y2);
            for(int i=0;i<m;i++) System.out.println(Arrays.toString(result[i]));
            System.out.println();*/
            int[] result = sl.getMinPath4(rows,cols,x1,y1,x2,y2);//在調試的時候程式輸出的是整個距離矩陣
            System.out.println(Arrays.toString(result));
            System.out.println();
        }
    }
}

最短路徑最短路徑

最短路徑

問題

如何有效存儲圖？

求解最短路徑

Solution1

Solution2

Solution3

Solution4

維特比算法

附錄：

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希