Dijkstra、BFS求有权图、无权图最短路径[Java]_bfs+贪心算法来求解最短路径java语言

一、Dijkstra算法解决有权图的最短路径问题

1. pre

	迪杰斯特拉算法采用贪心的策略，集合T{}用来存放当前已找到的最短路径节点集合。将起始点的路径权重赋
为0，当前节点不能到达的节点权重赋为无穷大。
1
2

2. 算法演示

下面展示的是无向带权值图求最短路径：

具体步骤：
每次添加路径最小值的节点到T集合。

结合图理解：

邻接表结构：链表头结点存放的是下标。

3. Java代码

题目：一共有n个点，m条无向边，每条边都有长度d和花费p，给定起点s终点t，要求输出起点到终点的最短距离
及其花费，如果最短距离有多条路线，则输出花费最少的。
输出：最小距离和花费。
1
2
3

创建Vertex类，构建邻接表：

class Edge {
	// 存放边的信息，next表示下一个节点，dist表示长度，cost表示花费
    int next;
    int dist;
    int cost;
    public Edge(int next, int dist, int cost) {
        this.next = next;
        this.dist = dist;
        this.cost = cost;
    }
}

class Vertex {
    int num;
    ArrayList<Edge> edge;  // 使用链表结构存储
    public Vertex(int num) {
        this.num = num;
        this.edge = new ArrayList<Edge>();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

ACM模式：

Scanner in = new Scanner(System.in);
while (in.hasNext()) {
	int n = in.nextInt(); // 点数
    int m = in.nextInt(); // 边数
    if (m == 0) break;
    Vertex[] list = new Vertex[n + 1];
    // 初始化Vertex
    for (int i = 1; i <= n; i++){
    	list[i] = new Vertex(i);
    }
    for (int i = 0; i < m; i++) {
        int a = in.nextInt();
        int b = in.nextInt();
        int dist = in.nextInt();  // 长度
        int cost = in.nextInt();  // 花费
        list[a].edge.add(new Edge(b, dist, cost));  // a->b 的长度和花费
        list[b].edge.add(new Edge(a, dist, cost));  
    }
    int s = in.nextInt(); // 起点
    int t = in.nextInt(); // 终点
    boolean[] marked = new boolean[n + 1];  // 用来记录当前节点是否更新
    int[] cost = new int[n + 1];
    int[] dist = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        cost[i] = Integer.MAX_VALUE;  // 初始花费设为max
        dist[i] = -1;  // 不可达用-1表示
        marked[i] = false;
    }
    dist[s] = 0;
    cost[s] = 0;
    marked[s] = true;
    int p = s;  // 当前起点p
    // Dijkstra
    for(int i=1;i<=n;i++){
      for(int j=0;j<list[p].edge.size();j++){
          int next = list[p].edge.get(j).next;
          int c = list[p].edge.get(j).cost;
          int d = list[p].edge.get(j).dist;
          if(marked[next]==true) continue;
          // 三种情况进行更新：距离未更新时、距离需更新时、距离相等花费变小时
          if(dist[next]==-1 || dist[next]>dist[p]+d || dist[next]== dist[p]+d && cost[next]>cost[p]+c){
              dist[next] = dist[p] + d;
              cost[next] = cost[p] + c;
          }
      }
      int min = Integer.MAX_VALUE;
      for(int j=1;j<=n;j++){
          if(marked[j]==true) continue;
          if(dist[j]==-1) continue;
          if(dist[j]<min){
              min = dist[j];
              p = j;
          }
      }
      marked[p] = true;
  }
  System.out.printf("%d %d\n", dist[t],cost[t]);
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

二、BFS算法解决无权图的最短路径问题

1. pre

广度优先搜索算法（BFS），是一种利用队列实现的搜索算法。

深度优先搜索算法（DFS），是一种利用递归实现的搜索算法。

2. 算法

题目：给定n个节点，节点从0依次编号，0固定为根节点，若节点设置障碍则不可达，输出从根节点到叶子结点的
路径（只有一条边相连的为叶子结点），否则输出NULL。
输入：
	第一行 n 【节点数】
	第二行 m 【边数】
	接下来m行 x y 【x与y相连】
	第m+3行 b 【接下来有b个障碍物节点】
	接下来b行 k 【节点k有障碍物】 
例：
	7
	6
	0 1
	0 3
	1 2
	3 4
	1 5
	5 6
	1
	4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

因为使用邻接表结构存储相邻节点，不要求是二叉树，为了方便画成树的形状。

同样的创建Vertex类，构建邻接表：

class Edge {
    int next;
    public Edge(int next) {
        this.next = next;
    }
}
class Vertex {
    int num;
    ArrayList<Edge> edge;
    public Vertex(int num) {
        this.num = num;
        this.edge = new ArrayList<Edge>();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

bfs

public static int bfs(int x, Vertex[] list, int[] book, int[] child){
   Queue<Integer> queue = new LinkedList<>();
   queue.offer(x);
   while (!queue.isEmpty()){
       int top = queue.poll();
       int size = list[top].edge.size();  // 相连的边的个数
       if (size == 0){
           return top;
       }else{
           for (int i = 0; i < size; i++) {
               int next = list[top].edge.get(i).next;
               if (book[next] == 1) continue;
               queue.offer(next);
               child[next] = top;
           }
       }
   }
   return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
    int n = scan.nextInt();
    int m = scan.nextInt();
    int[] child = new int[n];  
    Arrays.fill(child, -1);
    Vertex[] list = new Vertex[n];
    for (int i = 0; i < n; i++)
        list[i] = new Vertex(i);
    for (int i = 0; i < m; i++) {
        int a = scan.nextInt();
        int b = scan.nextInt();
        list[a].edge.add(new Edge(b));  // 单向
    }
    int block_num = scan.nextInt();
    int[] book = new int[n];
    for (int i = 0; i < block_num; i++) {
        int z = scan.nextInt();
        book[z] = 1;
    }
    int ans = bfs(0, list, book, child);
    if (ans == -1) {
        System.out.println("NULL");
    } else {
        Deque<Integer> res = new LinkedList<>();
        while (ans != -1) {
            res.addFirst(ans);
            ans = child[ans];
        }
        while (!res.isEmpty()) {
            System.out.print(res.poll() + " ");
        }
    }
}
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

例：