Dijkstra、Floyed 总结

大致顺序

  1. 构建图、赋值
  2. 根据 Floyed 或者 Dijkstra 算法或者节点之间的最小距离（ 一般为 dp[][] 或者 dist[] ）
  3. 最后根据题干获取答案

构建图、赋值

一般为：

public void init(int[][] grid, int k, int n) {
  
  // 1. 构造图
  int[][] dp = new int[n][n];
  int INF = Integer.MAX_VALUE / 2;
  
  // 任意节点之间的距离为 无限大
  // 节点本身之间的距离为 0
  for(int i = 0; i < n; i++) {
    Arrays.fill(dp, INF);
    dp[i][i] = 0;
  }
  
  // 2. 赋值
  for(int i = 0; i < grid.length; i++) {
    int x = grid[i][0] - 1;
    int y = grid[i][1] - 1;
    dp[x][y] = grid[i][2];
}

根据 Floyed 或者 Dijkstra 算法的核心部分

  1. Floyed

// 依次遍历每个节点
for(int k = 0; k < n; k++) {
  
  // 枚举所有距离
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      // 当前距离 或者 通过其他节点 最小
      dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
    }
  }
}

  1. Dijkstra
  • 从未加入的节点中选取一个 dist 最小的节点，收录进来
  • 更新收录节点周边节点的 dist
boolean[] visited = new boolean[n]; // 是否遍历过
int[] dist = new int[n]; // 存储源节点 k 到其他节点的最小距离
Arrays.fill(dist, INF);
dist[k - 1] = 0; // 节点本身的距离为 0 

for(int i = 0; i < n; i++) {
  
  int cur = -1;
  for(int j = 0; j < n; j++) {
    // 从未加入的节点中选取一个dist最小的节点，收录进来
    if(!visited[j] && ( cur == -1 || dist[cur] > dist[j]) {
      cur = j;
    }
  }
  visited[cur] = true;
       
  // 这里其实我感觉跟 Floyed 没什么区别, 都是一个意思
  // dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
  for(int j = 0; j < n; j++) {
    dist[j] = Math.min(dist[j], dist[cur] + dp[cur][j];
  }
}


Floyed、Dijkstra、Bellman-Ford

Dijkstra 迪杰斯特拉
  • Dijkstra 算法是通过选定的被访问节点，求一个顶点到其他顶点的最短路径，也就是单源最短路径
  • Dijkstra 算法只能解决边权重非负的最短路径问题
  • 属于贪心算法，时间复杂度为 O(n^2)

Floyed 弗洛伊德
  • Floyed 算法是任意两点之间的最短路径，是多源最短路径；每个节点都可以看作被访问节点，求每个节点到其他节点的最短路径
  • 属于动态规划算法，时间复杂度为 O(n^3)

Bellman-Ford 福特
  • Bellman-Ford 算法是解决单源最短路劲问题，支持边权重为负数的情况，多数适用于有额外的条件、例如：在k个中转之内、规定时间内到达等情况
  • 属于动态规划算法，时间复杂度为 O(VE) V: 顶点数量、E：边数
  • 我感觉几乎就是固定格式了

有向图

  • K 站中转内最便宜的航班
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[k + 2][n];

        // 初始化
        for(int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], INF);
        }

        // 初始化 0 到 src 的初始距离
        dp[0][src] = 0;

        // 枚举 n - 1条边
        for(int i = 1; i <= k + 1; i++) {
            for(int[] temp : flights) {
                int start = temp[0], end = temp[1], cost = temp[2];
                dp[i][end] = Math.min(dp[i][end], dp[i - 1][start] + cost);
            }
        }

        int res = INF;
        for(int i = 1; i <= k + 1; i++) {
            res = Math.min(res, dp[i][dst]);
        }

        return res == INF ? -1 : res;
    }
}

无向图

  • 多一步 dp
  • 规定时间内到达终点的最小花费
class Solution {
    public int minCost(int maxTime, int[][] edges, int[] passingFees) {
        int n = passingFees.length;
        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[maxTime + 1][n];
        for(int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], INF);
        }

        dp[0][0] = passingFees[0];

        for(int i = 1; i <= maxTime; i++) {
            for(int[] temp : edges) {
                int start = temp[0], end = temp[1], cost = temp[2];
                if(i >= cost) {
                    dp[i][end] = Math.min(dp[i][end], dp[i - cost][start] + passingFees[end]);
                    dp[i][start] = Math.min(dp[i][start], dp[i - cost][end] + passingFees[start]);
                }
            }
        }

        int res = INF;
        for(int i = 1; i <= maxTime; i++) {
            res = Math.min(res, dp[i][n - 1]);
        }

        return res == INF ? -1 : res;
    }
}


典型题目