class065 A星、Floyd、Bellman-Ford与SPFA【算法】

package class065;
import java.util.PriorityQueue;
// A*算法模版（对数器验证）
public class Code01_AStarAlgorithm {
  // 0:上，1:右，2:下，3:左
  public static int[] move = new int[] { -1, 0, 1, 0, -1 };
  // Dijkstra算法
  // grid[i][j] == 0 代表障碍
  // grid[i][j] == 1 代表道路
  // 只能走上、下、左、右，不包括斜线方向
  // 返回从(startX, startY)到(targetX, targetY)的最短距离
  public static int minDistance1(int[][] grid, int startX, int startY, int targetX, int targetY) {
    if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) {
      return -1;
    }
    int n = grid.length;
    int m = grid[0].length;
    int[][] distance = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
    distance[startX][startY] = 1;
    boolean[][] visited = new boolean[n][m];
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    // 0 : 行
    // 1 : 列
    // 2 : 从源点出发到达当前点的距离
    heap.add(new int[] { startX, startY, 1 });
    while (!heap.isEmpty()) {
      int[] cur = heap.poll();
      int x = cur[0];
      int y = cur[1];
      if (visited[x][y]) {
        continue;
      }
      visited[x][y] = true;
      if (x == targetX && y == targetY) {
        return distance[x][y];
      }
      for (int i = 0, nx, ny; i < 4; i++) {
        nx = x + move[i];
        ny = y + move[i + 1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny]
            && distance[x][y] + 1 < distance[nx][ny]) {
          distance[nx][ny] = distance[x][y] + 1;
          heap.add(new int[] { nx, ny, distance[x][y] + 1 });
        }
      }
    }
    return -1;
  }
  // A*算法
  // grid[i][j] == 0 代表障碍
  // grid[i][j] == 1 代表道路
  // 只能走上、下、左、右，不包括斜线方向
  // 返回从(startX, startY)到(targetX, targetY)的最短距离
  public static int minDistance2(int[][] grid, int startX, int startY, int targetX, int targetY) {
    if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) {
      return -1;
    }
    int n = grid.length;
    int m = grid[0].length;
    int[][] distance = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
    distance[startX][startY] = 1;
    boolean[][] visited = new boolean[n][m];
    // 0 : 行
    // 1 : 列
    // 2 : 从源点出发到达当前点的距离 + 当前点到终点的预估距离
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    heap.add(new int[] { startX, startY, 1 + f1(startX, startY, targetX, targetY) });
    while (!heap.isEmpty()) {
      int[] cur = heap.poll();
      int x = cur[0];
      int y = cur[1];
      if (visited[x][y]) {
        continue;
      }
      visited[x][y] = true;
      if (x == targetX && y == targetY) {
        return distance[x][y];
      }
      for (int i = 0, nx, ny; i < 4; i++) {
        nx = x + move[i];
        ny = y + move[i + 1];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny]
            && distance[x][y] + 1 < distance[nx][ny]) {
          distance[nx][ny] = distance[x][y] + 1;
          heap.add(new int[] { nx, ny, distance[x][y] + 1 + f1(nx, ny, targetX, targetY) });
        }
      }
    }
    return -1;
  }
  // 曼哈顿距离
  public static int f1(int x, int y, int targetX, int targetY) {
    return (Math.abs(targetX - x) + Math.abs(targetY - y));
  }
  // 对角线距离
  public static int f2(int x, int y, int targetX, int targetY) {
    return Math.max(Math.abs(targetX - x), Math.abs(targetY - y));
  }
  // 欧式距离
  public static double f3(int x, int y, int targetX, int targetY) {
    return Math.sqrt(Math.pow(targetX - x, 2) + Math.pow(targetY - y, 2));
  }
  // 为了测试
  public static int[][] randomGrid(int n) {
    int[][] grid = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (Math.random() < 0.3) {
          // 每个格子有30%概率是0
          grid[i][j] = 0;
        } else {
          // 每个格子有70%概率是1
          grid[i][j] = 1;
        }
      }
    }
    return grid;
  }
  // 为了测试
  public static void main(String[] args) {
    int len = 100;
    int testTime = 10000;
    System.out.println("功能测试开始");
    for (int i = 0; i < testTime; i++) {
      int n = (int) (Math.random() * len) + 2;
      int[][] grid = randomGrid(n);
      int startX = (int) (Math.random() * n);
      int startY = (int) (Math.random() * n);
      int targetX = (int) (Math.random() * n);
      int targetY = (int) (Math.random() * n);
      int ans1 = minDistance1(grid, startX, startY, targetX, targetY);
      int ans2 = minDistance2(grid, startX, startY, targetX, targetY);
      if (ans1 != ans2) {
        System.out.println("出错了!");
      }
    }
    System.out.println("功能测试结束");
    System.out.println("性能测试开始");
    int[][] grid = randomGrid(4000);
    int startX = 0;
    int startY = 0;
    int targetX = 3900;
    int targetY = 3900;
    long start, end;
    start = System.currentTimeMillis();
    int ans1 = minDistance1(grid, startX, startY, targetX, targetY);
    end = System.currentTimeMillis();
    System.out.println("运行dijskra算法结果: " + ans1 + ", 运行时间(毫秒) : " + (end - start));
    start = System.currentTimeMillis();
    int ans2 = minDistance2(grid, startX, startY, targetX, targetY);
    end = System.currentTimeMillis();
    System.out.println("运行A*算法结果: " + ans2 + ", 运行时间(毫秒) : " + (end - start));
    System.out.println("性能测试结束");
  }
}

package class065;
// Floyd算法模版（洛谷）
// 测试链接 : https://www.luogu.com.cn/problem/P2910
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code02_Floyd {
  public static int MAXN = 101;
  public static int MAXM = 10001;
  public static int[] path = new int[MAXM];
  public static int[][] distance = new int[MAXN][MAXN];
  public static int n, m, ans;
  // 初始时设置任意两点之间的最短距离为无穷大，表示任何路不存在
  public static void build() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        distance[i][j] = Integer.MAX_VALUE;
      }
    }
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      m = (int) in.nval;
      for (int i = 0; i < m; i++) {
        in.nextToken();
        path[i] = (int) in.nval - 1;
      }
      // 这道题给的图是邻接矩阵的形式
      // 任意两点之间的边权都会给定
      // 所以显得distance初始化不太必要
      // 但是一般情况下，distance初始化一定要做
      build();
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          in.nextToken();
          distance[i][j] = (int) in.nval;
        }
      }
      floyd();
      ans = 0;
      for (int i = 1; i < m; i++) {
        ans += distance[path[i - 1]][path[i]];
      }
      out.println(ans);
    }
    out.flush();
    out.close();
    br.close();
  }
  public static void floyd() {
    // O(N^3)的过程
    // 枚举每个跳板
    // 注意，跳板要最先枚举！跳板要最先枚举！跳板要最先枚举！
    for (int bridge = 0; bridge < n; bridge++) { // 跳板
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          // i -> .....bridge .... -> j
          // distance[i][j]能不能缩短
          // distance[i][j] = min ( distance[i][j] , distance[i][bridge] + distance[bridge][j])
          if (distance[i][bridge] != Integer.MAX_VALUE 
              && distance[bridge][j] != Integer.MAX_VALUE
              && distance[i][j] > distance[i][bridge] + distance[bridge][j]) {
            distance[i][j] = distance[i][bridge] + distance[bridge][j];
          }
        }
      }
    }
  }
}

package class065;
import java.util.Arrays;
// Bellman-Ford算法应用（不是模版）
// k站中转内最便宜的航班
// 有 n 个城市通过一些航班连接。给你一个数组 flights
// 其中 flights[i] = [fromi, toi, pricei]
// 表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
// 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线
// 使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
// 测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/
public class Code03_BellmanFord {
  // Bellman-Ford算法
  // 针对此题改写了松弛逻辑，课上讲了细节
  public static int findCheapestPrice(int n, int[][] flights, int start, int target, int k) {
    int[] cur = new int[n];
    Arrays.fill(cur, Integer.MAX_VALUE);
    cur[start] = 0;
    for (int i = 0; i <= k; i++) {
      int[] next = Arrays.copyOf(cur, n);
      for (int[] edge : flights) {
        // a -> b , w
        if (cur[edge[0]] != Integer.MAX_VALUE) {
          next[edge[1]] = Math.min(next[edge[1]], cur[edge[0]] + edge[2]);
        }
      }
      cur = next;
    }
    return cur[target] == Integer.MAX_VALUE ? -1 : cur[target];
  }
}

package class065;
// Bellman-Ford + SPFA优化模版（洛谷）
// 给定一个 n个点的有向图，请求出图中是否存在从顶点 1 出发能到达的负环
// 负环的定义是：一条边权之和为负数的回路。
// 测试链接 : https://www.luogu.com.cn/problem/P3385
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Code04_SPFA {
  public static int MAXN = 2001;
  public static int MAXM = 6001;
  // 链式前向星建图需要
  public static int[] head = new int[MAXN];
  public static int[] next = new int[MAXM];
  public static int[] to = new int[MAXM];
  public static int[] weight = new int[MAXM];
  public static int cnt;
  // SPFA需要
  public static int MAXQ = 4000001;
  // 源点出发到每个节点的距离表
  public static int[] distance = new int[MAXN];
  // 节点被松弛的次数
  public static int[] updateCnt = new int[MAXN];
  // 哪些节点被松弛了放入队列
  public static int[] queue = new int[MAXQ];
  public static int l, r;
  // 节点是否已经在队列中
  public static boolean[] enter = new boolean[MAXN];
  public static void build(int n) {
    cnt = 1;
    l = r = 0;
    Arrays.fill(head, 1, n + 1, 0);
    Arrays.fill(enter, 1, n + 1, false);
    Arrays.fill(distance, 1, n + 1, Integer.MAX_VALUE);
    Arrays.fill(updateCnt, 1, n + 1, 0);
  }
  public static void addEdge(int u, int v, int w) {
    next[cnt] = head[u];
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt++;
  }
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    in.nextToken();
    int cases = (int) in.nval;
    for (int i = 0, n, m; i < cases; i++) {
      in.nextToken(); n = (int) in.nval;
      in.nextToken(); m = (int) in.nval;
      build(n);
      for (int j = 0, u, v, w; j < m; j++) {
        in.nextToken(); u = (int) in.nval;
        in.nextToken(); v = (int) in.nval;
        in.nextToken(); w = (int) in.nval;
        if (w >= 0) {
          addEdge(u, v, w);
          addEdge(v, u, w);
        } else {
          addEdge(u, v, w);
        }
      }
      out.println(spfa(n) ? "YES" : "NO");
    }
    out.flush();
    out.close();
    br.close();
  }
  // Bellman-Ford + SPFA优化的模版
  public static boolean spfa(int n) {
    distance[1] = 0;
    updateCnt[1]++;
    queue[r++] = 1;
    enter[1] = true;
    while (l < r) {
      int u = queue[l++];
      enter[u] = false;
      for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {
        v = to[ei];
        w = weight[ei];
        if (distance[u] + w < distance[v]) {
          distance[v] = distance[u] + w;
          if (!enter[v]) {
            if (updateCnt[v]++ == n) {
              return true;
            }
            queue[r++] = v;
            enter[v] = true;
          }
        }
      }
    }
    return false;
  }
}