最短路径问题即：找出一个点到另一个点的最短路径。这类问题的解法有：
1.动态规划（DP）
以为63. Minimum Path Sum例，遍历方向只有右和下且目的地为最后一个节点，所以任意一个节点最终都能到达目的节点，此时只需要把所有节点遍历，并简单的记录每一个节点的最短路径就可以解决问题：
class Solution {
public int minPathSum(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (i > 0 && j > 0) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j-1]);
} else if (i > 0) {
grid[i][j] += grid[i - 1][j];
} else if (j > 0) {
grid[i][j] += grid[i][j - 1];
}
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
}
时间复杂度为O(m*n)。
2.Floyd 算法
以743. Network Delay Time为例，这一题本质就是求两个点之间的最短距离，还是沿用上面的思路来解决。
-
通过一个二维数据来记录各个点到另一个点的延迟。
-
当不经过其他点时，两个点的最短延迟就是二维数组中记录的数据。
-
假设现在必须只经过点c，则两点之间的最低延迟为
$$ L_ {ab} = min(L_{ ab }, \quad L_{ac} + L_{cb}) $$
- 假设现在必须经过点c、d，则两点之间的最低延迟为
$$ L_{ab} = min(min(L_{ab}, L_{ac} + L_{cb}),\quad min(L_{ab},L_{ad} + L_{db})) $$
因此，经过所有点时的延迟可以通过遍历所有点，套用上述公式得到：
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
Integer dp[][] = new Integer[N + 1][N + 1];
for (int[] time : times) {
dp[time[0]][time[1]] = time[2];
}
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dp[i][k] != null && dp[k][j] != null) {
if (dp[i][j] == null) {
dp[i][j] = dp[i][k] + dp[k][j];
} else {
dp[i][j] = Math.min(dp[i][k] + dp[k][j], dp[i][j]);
}
}
}
}
}
int max = 0;
for (int i = 1; i <= N; i++) {
if (i != K) {
if (dp[K][i] == null) return -1;
max = Math.max(max, dp[K][i]);
}
}
return max;
}
}
时间复杂度为O(n^3)
关于此算法更详细的介绍可以参考：https://wiki.jikexueyuan.com/project/easy-learn-algorithm/floyd.html
3.迪杰斯特拉算法（Dijkstra）
还是以Network Delay Time问题为例，使用Floyd算法可以得出图中所有点到点的最短路径，这称为多源最短路径算法，但是实际上这个问题中，只需要求点K到其余各点的最短距离，所以这里介绍一种新的算法：Dijkstra。
- 同样还是使用二维数据记录各点的距离。
- 另外用一个单独的数据记录各点到指定点K的最短距离。
- 找到距离K最近的点A，并看看A指向的点是否能通过A来缩短与K的距离，并将距离记录到2中的数组，这个过程称为松弛
- 继续通过3中的方法，直到所有点都松弛完成，2中数组保存的就是最短的点
class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
Integer dp[][] = new Integer[N + 1][N + 1];
Integer min[] = new Integer[N + 1];
boolean finished[] = new boolean[N + 1];
for (int[] time : times) {
dp[time[0]][time[1]] = time[2];
if (time[0] == K) min[time[1]] = time[2];
}
for (int i = 1; i <= N; i++) {
int minIndex = -1;
for (int j = 1; j <= N; j++) {
if (j != K && min[j] != null && !finished[j]) {
minIndex = minIndex < 0 ? j : (min[j] <= min[minIndex] ? j : minIndex);
}
}
if (minIndex > 0) {
finished[minIndex] = true;
for (int j = 1; j <=N; j++) {
if (j != K && dp[minIndex][j] != null) {
min[j] = min[j] == null ? min[minIndex] + dp[minIndex][j] : Math.min(min[j], min[minIndex] + dp[minIndex][j]);
}
}
}
}
int max = 0;
for (int i = 1; i <= N; i++) {
if (i != K) {
if (min[i] == null) return -1;
max = Math.max(max, min[i]);
}
}
return max;
}
}
时间复杂度为O(n^2)
关于此算法更详细的介绍可以参考：
https://wiki.jikexueyuan.com/project/easy-learn-algorithm/dijkstra.html