最短路径--城市路径问题：

问题描述：求从1号城市到5号城市的最短路径长度 city Input： 5 8 1 2 2 1 5 10 2 3 3 2 5 7 3 1 4 3 4 4 4 5 5 5 3 3 Output： 9

DFS 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.Scanner;
public class minPath {
    static int min = 99999999;
    static int[][] e = new int[100][100];
    static int[] book = new int[100];
    static int n, m;
    static Scanner input = new Scanner(System.in);

    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    e[i][j] = 99999999;
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();
            e[a][b] = c;
        }

        book[1] = 1;
        dfs(1, 0);
        System.out.println(min);
    }

    public static void dfs(int cur, int dis) {
        /**
         * 如果当前路径大于之前找到的最小值，可直接返回
         * */
        if (dis > min) {
            return;
        }
        /**
         * 判断是否达到最后一个结点，更新最小值，返回
         * */
        if(cur == n) {
            if (dis < min) {
                min = dis;
                return;
            }
        }
        /**
         * 当前点到其他各点之间可连通但是还未添加进来时，遍历执行
         * */
        for (int i = 1; i <= n; i++) {
            if (e[cur][i] != 99999999 && book[i] == 0) {
                book[i] = 1;
                dfs(i, dis+e[cur][i]);
                /**
                 * 回溯
                 **/
                book[i] = 0;
            }
        }
        return;
    }
}

最短路径--转乘问题：

问题描述：求从1号城市到5号城市的最短路径长度 Input： 5 7 1 5 1 2 1 3 2 3 2 4 3 4 3 5 4 5 Output： 2 path2 这个题目与上一个的区别就在于，这些路径是没有权值的，也就是说只需要找出到达一个点的最短距离就可以了，记录次数即可。

BFS 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class node {
    int x;
    int s;
    node(int x, int s) {
        this.x = x;
        this.s = s;
    }
}

public class minPath {
    static int[][] e = new int[51][51];
    static int[] book = new int[51];
    static int n, m;
    static int start, end;
    static int mark, sum;
    static Queue<node> queue = new LinkedList<>();
    static Scanner input = new Scanner(System.in);
    public static void main(String[] args) {
        n = input.nextInt();
        m = input.nextInt();
        start = input.nextInt();
        end = input.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    e[i][j] = 99999999;
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            int a = input.nextInt();
            int b = input.nextInt();
            e[a][b] = 1;
            e[b][a] = 1;
        }

        queue.offer(new node(start, 0));
        book[1] = start;

        bfs();
        System.out.println(sum);
    }
    public static void bfs() {
        int flag = 0;
        while (!queue.isEmpty()) {
            int cur = queue.peek().x;
            for (int i = 1; i <= n; i++) {
                if(e[cur][i] != 99999999 && book[i] == 0) {
                    mark = i;
                    sum = queue.peek().s + 1;
                    queue.offer(new node(i, sum));
                    book[i] = 1;
                }
                if(mark == end) {
                    flag = 1;
                    break;
                }
            }
            if(flag == 1) {
                break;
            }
            queue.remove();
        }
        return;
    }
}

基本上能用深度优先的问题都可以用广度优先，但是广度优先更适合无向图，或者说所有边的权值一样的情况，大家可以通过多做题灵活使用这两种方法