深搜尋找最短路徑

原創

尋求圖中最短路徑的方法有很多，最近剛開始學習，先用深搜實現，用鄰接矩陣來存儲圖。

直接上圖上代碼：

尋求從0~4的最短路徑 

利用深搜找出所有從0~4的路徑，一一比較選擇出最小的

import java.util.*;

public class 城市地圖 {
    
    static int v;    //頂點
    static int e;    //邊
    static int matrix[][];    //鄰接矩陣
    static int book[];    //標記
    static int min=99999;
    
    static void dfs(int point,int distinct) {
        if(distinct>min) {
            return;
        }
        if(point==v-1) {    //目標點是v-1
            if(distinct<min) {
                min=distinct;
                return;
            }
        }
        for(int i=0;i<v;i++) {
            if(matrix[point][i]>0 && matrix[point][i]<99999 && book[i]==0) {
                book[i]=1;
                dfs(i,distinct+matrix[point][i]);
                book[i]=0;    //回溯
            }
        }
        return;
    }

    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        v=reader.nextInt();
        e=reader.nextInt();
        matrix=new int[v][v];
        book=new int[v];
        //矩陣初始化
        for(int i=0;i<v;i++) {
            book[i]=0;
            for(int j=0;j<v;j++) {
                if(i==j) {
                    matrix[i][j]=0;
                }
                else {
                    matrix[i][j]=99999;
                }
            }
        }
        //讀入邊
        for(int i=0;i<e;i++) {
            int first=reader.nextInt();
            int second=reader.nextInt();
            int dis=reader.nextInt();
            matrix[first][second]=dis;    //有向圖
        }
        book[0]=1;    //起始點是0
        dfs(0,0);
        System.out.println(min);
    }
}

測試數據：

輸入：

5 8

0 1 2

0 4 10

1 2 3

1 4 7

2 0 4

2 3 4

3 4 5

4 2 3

輸出：9

 無向圖代碼：

import java.util.*;

public class 城市地圖_無向 {
    
    static int v;
    static int e;
    static int matrix[][];
    static int book[];
    static int min=99999;
    
    static void dfs(int point,int dis) {
        if(dis>min) {
            return;
        }
        if(point==v-1) {    //到達目的地
            if(dis<min) {
                min=dis;
            }
            return;
        }
        for(int i=0;i<v;i++) {
            if(matrix[point][i]>0 && matrix[point][i]<99999 && book[i]==0) {
                book[i]=1;
                dfs(i,dis+matrix[point][i]);
                book[i]=0;    //回溯
            }
        }
    }

    public static void main(String[] args) {
        Scanner reader=new Scanner(System.in);
        v=reader.nextInt();
        e=reader.nextInt();
        matrix=new int[v][v];
        book=new int[v];
        //矩陣初始化
        for(int i=0;i<v;i++) {
            book[i]=0;
            for(int j=0;j<v;j++) {
                if(i==j) {
                    matrix[i][j]=0;
                }
                else {
                    matrix[i][j]=99999;
                }
            }
        }
        //讀入邊
        for(int i=0;i<e;i++) {
            int edge_One=reader.nextInt();
            int edge_Two=reader.nextInt();
            int value=reader.nextInt();
            matrix[edge_One][edge_Two]=value;    //無向圖
            matrix[edge_Two][edge_One]=value;
        }
        book[0]=1;
        dfs(0,0);
        System.out.println(min);
    }

}

測試用例：

輸入：

5 8

0 1 2

0 4 10

1 2 3

1 4 7

2 0 4

2 3 4

3 4 5

4 2 3

輸出：7

23:40:24

2018-07-23