最短路径问题

743 网络延迟时间

dijkstra算法

class Solution {
    int N = 100, M = 6000;
    int[][] w = new int[N][N];
    int n, k;
    int INF = 0x3f3f3f3f; // 不能选MAX_VALUE 可能会超空间
    boolean[] vis = new boolean[N];
    int[] dist = new int[N];
    public int networkDelayTime(int[][] times, int _n, int _k) {
        n = _n; k = _k;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 自己到自己为0，其它为INF
                w[i][j] = w[j][i] = i == j ? 0 : INF; 
            }
        }
        
        for (int[] time : times) {
            int u = time[0];
            int v = time[1];
            int c = time[2];
            // 有向图，只能更新一条边
            w[u][v] = c;   
        }

        dijkstra();

        int res = 0;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, dist[i]);
        }
        return res > INF / 2 ? -1 : res;
    }

    public void dijkstra() {
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);

        dist[k] = 0;

        // 一共需要查找n次，每个节点都要遍历到
        for (int i = 1; i <= n; i++) {
            int t = -1;
            // 找到到起点的最短路径
            for (int j = 1; j <= n; j++) {
                // t = -1 表示找到的第一个节点
                if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            vis[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + w[t][j]);
            }
        }
    }
}

787. K 站中转内最便宜的航班

bellman ford 算法

class Solution {
    int N = 110, INF = 0x3f3f3f3f;
    int[][] g= new int[N][N];
    int[] dist = new int[N];
    int n, m, s, t, k;
    public int findCheapestPrice(int _n, int[][] flights, 
    int _src, int _dst, int _k) {
        n = _n; s = _src; t = _dst; k = _k + 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                g[i][j] = i == j ? 0 : INF;
            }
        }

        for (int[] f : flights) {
            int u = f[0], v = f[1], w = f[2];
            g[u][v] = w;
        }
        int ans = bf();
        return ans > INF / 2 ? -1 : ans;
    }

    int bf() {
        Arrays.fill(dist, INF);
        dist[s] = 0;

        for (int limit = 0; limit < k; limit++) {
            int[] clone = dist.clone();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[j] = Math.min(dist[j], clone[i] + g[i][j]);
                }
            }
        }
        return dist[t];
    }
}