4.2.1 单点最短路径

  • 问题:给定一幅图和一个起点s,问从s到给定顶点v是否存在一条路径?如果有,找出其中最短的一条
  • 思路:要找到s到v的最短路径,从s开始,在所有的距离为1的点中找v,如果没有,则到距离为2的点中找v,如此反复

广度优先搜索(BFS)和深度优先搜索(DFS)

  • DFS:选用递归(隐式栈),使用LIFO规则从有带搜索的通道中选择最晚遇到的那条往下走
  • BFS:按照与起点的距离顺序来遍历所有顶点,使用(FIFO)队列实现,从有带搜索的通道中选择最早遇到的那条

实现

  1. public class BreadthFirstPaths {
  2.     private boolean[] marked;//是否之前已有更短路径到达
  3.     private int[] edgeTo;//到达该结点已知路径上的最后顶点
  4.     private final int s;
  6.     public BreadthFirstPaths(Graph G, int s){
  7.         marked = new boolean[G.V()];
  8.         edgeTo = new int[G.V()];
  9.         this.s = s;
  10.         bfs(G,s);
  11.     }
  12.     (队列)
  13.     public void bfs(Graph G, int s){
  14.         Queue<Integer> queue = new Queue<>();
  15.         marked[s] = true;
  16.         queue.enqueue(s);
  17.         while (! queue.isEmpty()){
  18.             int v = queue.dequeue();
  19.             for (int w: G.adj(v)){
  20.                 if (!marked[w]){
  21.                     edgeTo[w] = v;//保存已知路径最后一个顶点
  22.                     marked[w] = true;//标记为已达点
  23.                     queue.enqueue(w);//添加至队列
  24.                 }
  25.             }
  26.         }
  27.     }
  29.     private boolean hasPathTo(int v){ return marked[v]; }
  31.     //返回s到v的最短路径
  32.     public Iterable<Integer> pathTo(int v){
  33.         if (!hasPathTo(v)) return null;
  34.         Stack<Integer> path = new Stack<>();
  35.         for (int i = v; i != s; i = edgeTo[i])
  36.             path.push(i);
  37.         path.push(v);
  38.         return path;
  39.     }
  40. }
  • 虽然和DFS的pathTo()实现方法一样但BFS会给出s到v的一段最短路径

算法分析

  • 对于从s可达的任意顶点v,BFS都可以找到一条从s到v的最短路径
  • BFS搜索时间在最坏情况下和V+E成正比

BFS和DFS对比

  • 相同点:
    • 搜索时都会先将起点存入数据结构中,然后重复一下操作指导数据结构被清空
      • 取下一个顶点并标记
      • 将v的所有相邻而又未被标记的顶点继续加入数据结构
  • 不同点:
    • DFS选取递归/隐式栈,每次将最晚一个加入的结点当作下一个顶点
    • BFS选取队列,每次将最早一个加入的结点当作下一个顶点