最短路
大约 4 分钟
最短路
| 题目 | 难度 | |
|---|---|---|
| 743. 网络延迟时间 | 中等 | |
| 787. K 站中转内最便宜的航班 | 中等 | |
| 1928. 规定时间内到达终点的最小花费 | 困难 |
Floyd 算法
时间复杂度：O(n^3)。
class Solution743 {
private static final int INF = Integer.MAX_VALUE / 2;
public int networkDelayTime(int[][] times, int n, int k) {
// 有 n 个网络节点，标记为 1 到 n
// 邻接矩阵 weights[ui][vi] = wi 表示从 ui 到 vi 有权重为 wi 的边
int[][] weights = buildAdj(times, n);
// floyd 基本流程为三层循环：
// 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
for (int p = 1; p <= n; p++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
weights[i][j] = Math.min(weights[i][j], weights[i][p] + weights[p][j]);
}
}
}
// 遍历答案
int max = 0;
for (int i = 1; i <= n; i++) {
max = Math.max(max, weights[k][i]);
}
return max == INF ? -1 : max;
}
private int[][] buildAdj(int[][] times, int n) {
int[][] weights = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
weights[i][j] = weights[j][i] = 0;
} else {
weights[i][j] = weights[j][i] = INF;
}
}
}
for (int[] time : times) {
int ui = time[0];
int vi = time[1];
int wi = time[2];
weights[ui][vi] = wi;
}
return weights;
}
}
Dijkstra 算法
Dijkstra 求解 非负权图 上单源最短路径的算法。时间复杂度：O(n^2) / O(mlogn)。
邻接数组 + 堆优化 dijkstra
class Solution743 {
private static final int INF = 100 * 100 + 1;
public int networkDelayTime(int[][] times, int n, int k) {
// 邻接矩阵
int[][] adj = new int[n + 1][n + 1];
for (int u = 1; u <= n; u++) {
for (int v = 1; v <= n; v++) {
adj[u][v] = u == v ? 0 : INF;
}
}
for (int[] time : times) {
adj[time[0]][time[1]] = time[2];
}
// dijkstra
boolean[] visited = new boolean[n + 1];
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
// 优先队列优化
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
priorityQueue.add(new int[]{k, 0});
dist[k] = 0;
while (!priorityQueue.isEmpty()) {
int[] top = priorityQueue.remove();
int u = top[0];
if (visited[u]) {
continue;
}
visited[u] = true;
for (int v = 1; v <= n; v++) {
if (u != v && adj[u][v] != INF) {
if (dist[v] > dist[u] + adj[u][v]) {
dist[v] = dist[u] + adj[u][v];
priorityQueue.add(new int[]{v, dist[v]});
}
}
}
}
// 遍历答案
int max = 0;
for (int i = 1; i <= n; i++) {
max = Math.max(max, dist[i]);
}
return max == INF ? -1 : max;
}
}
集合类 + 堆优化 dijkstra
class Solution743 {
private static final int INF = 100 * 100 + 1;
public int networkDelayTime(int[][] times, int n, int k) {
// 邻接矩阵
Map<Integer, List<int[]>> adj = new HashMap<>();
for (int[] time : times) {
adj.computeIfAbsent(time[0], key -> new ArrayList<>()).add(new int[]{time[1], time[2]});
}
// dijkstra
boolean[] visited = new boolean[n + 1];
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
// 优先队列优化
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
priorityQueue.add(new int[]{k, 0});
dist[k] = 0;
while (!priorityQueue.isEmpty()) {
int[] top = priorityQueue.remove();
int u = top[0];
if (visited[u]) {
continue;
}
visited[u] = true;
for (int[] tuple : adj.getOrDefault(u, new ArrayList<>())) {
int v = tuple[0];
int w = tuple[1];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
priorityQueue.add(new int[]{v, dist[v]});
}
}
}
// 遍历答案
int max = 0;
for (int i = 1; i <= n; i++) {
max = Math.max(max, dist[i]);
}
return max == INF ? -1 : max;
}
}
链式前向星 + 堆优化 dijkstra
class Solution743 {
private static final int INF = 100 * 100 + 1;
// 链式前向星
private int[] he, ne, ed, we;
private int idx;
void add(int u, int v, int w) {
ed[idx] = v;
ne[idx] = he[u];
he[u] = idx;
we[idx] = w;
idx++;
}
public int networkDelayTime(int[][] times, int n, int k) {
int m = times.length;
// 链式前向星
he = new int[n + 1];
Arrays.fill(he, -1);
ne = new int[m];
ed = new int[m];
we = new int[m];
idx = 0;
for (int[] time : times) {
add(time[0], time[1], time[2]);
}
// dijkstra
boolean[] visited = new boolean[n + 1];
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
// 优先队列优化
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
priorityQueue.add(new int[]{k, 0});
dist[k] = 0;
while (!priorityQueue.isEmpty()) {
int[] top = priorityQueue.remove();
int u = top[0];
if (visited[u]) {
continue;
}
visited[u] = true;
for (int i = he[u]; i != -1; i = ne[i]) {
int v = ed[i];
int w = we[i];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
priorityQueue.add(new int[]{v, dist[v]});
}
}
}
// 遍历答案
int max = 0;
for (int i = 1; i <= n; i++) {
max = Math.max(max, dist[i]);
}
return max == INF ? -1 : max;
}
}
Bellman ford 算法
Bellman ford 可以求出有负权的图的最短路 时间复杂度 O(mn)
787. K 站中转内最便宜的航班
import java.util.Arrays;
public class Solution787 {
private static final int INF = 100 * 10000 + 1;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// bellman ford 算法
// 最多只能中转 k 次，即最多搭乘 k+1 次航班
// dp[t][i] 表示通过恰好 t 次航班，从出发城市 src 到达城市 i 需要的最小花费。
int[][] dp = new int[k + 2][n];
for (int[] ints : dp) {
Arrays.fill(ints, INF);
}
dp[0][src] = 0;
for (int t = 1; t <= k + 1; t++) {
for (int[] flight : flights) {
int from = flight[0];
int to = flight[1];
int price = flight[2];
dp[t][to] = Math.min(dp[t][to], dp[t - 1][from] + price);
}
}
// 取 dp[1][dst], dp[2][dst], ... dp[k+1][dst] 最小值
int min = INF;
for (int t = 1; t <= k + 1; t++) {
min = Math.min(min, dp[t][dst]);
}
return min == INF ? -1 : min;
}
}
1928. 规定时间内到达终点的最小花费
import java.util.Arrays;
public class Solution1928 {
private static final int INF = 1000 * 1000 + 1;
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length;
// bellman ford 算法
// dp[t][i] 表示通过恰好 t 分钟到达城市 i 需要的最少通行费总和
int[][] dp = new int[maxTime + 1][n];
for (int[] ints : dp) {
Arrays.fill(ints, INF);
}
dp[0][0] = passingFees[0];
for (int t = 1; t <= maxTime; t++) {
for (int[] edge : edges) {
int from = edge[0];
int to = edge[1];
int cost = edge[2];
if (cost <= t) {
// 双向通路
dp[t][to] = Math.min(dp[t][to], dp[t - cost][from] + passingFees[to]);
dp[t][from] = Math.min(dp[t][from], dp[t - cost][to] + passingFees[from]);
}
}
}
int min = INF;
for (int t = 1; t <= maxTime; t++) {
min = Math.min(min, dp[t][n - 1]);
}
return min == INF ? -1 : min;
}
}
参考链接
（全文完）