### 题目

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

### 抽象成数学模型

1. Dijkstra算法
2. Bellman-Ford算法
3. Floyd-Warshall算法
4. 动态规划 + 广度优先查找

### Dijkstra算法

Dijkstra的本质是一个“贪心算法”。它的核心理念是：

从0出发，当前子图只有[0]节点
0 可以到 2, 4

0->7 = 0->2 + 2->7 = 0.60，将0->7=0.60压入PriorityQueue

0->5 = 0->4 + 4->5 = 0.73，将0->5=0.73压入PriorityQueue
0->7 = 0->4 + 4->7 = 0.75，将0->7=0.75压入PriorityQueue。注意此时队列中有两个0->7: 0.60和0.75
... ...

... ...


Dijkstra算法包含了动态规划的思想，因为每次纳入子图的都是确定的最短的路线，因此可以被作为以后问题的子问题的已知最优解。

#### 代码

class Solution {
private class Flight {
int dest, cost;
private Flight(int dest, int cost) {
this.dest = dest;
this.cost = cost;
}
}
public int networkDelayTime(int[][] times, int N, int K) {
int[][] flightTable = new int[N + 1][N + 1];
for (int[] row : flightTable) Arrays.fill(row, -1);
for (int i = 1; i <= N; i++) flightTable[i][i] = 0;
for (int[] time : times) flightTable[time[0]][time[1]] = time[2];
PriorityQueue<Flight> heap = new PriorityQueue<>((Flight a, Flight b) -> (a.cost - b.cost));
boolean[] visited = new boolean[N + 1];
int[] minCosts = new int[N + 1];
Arrays.fill(minCosts, Integer.MAX_VALUE);
int remain = N;
int maxPrice = 0;
while (!heap.isEmpty()) {
Flight cheapest = heap.poll();
int from = cheapest.dest;
if (visited[from]) continue;
visited[from] = true;
maxPrice = Math.max(maxPrice, cheapest.cost);
remain--;
for (int to = 1; to <= N; to++) {
if (!visited[to] && flightTable[from][to] >= 0) {
int newPrice = cheapest.cost + flightTable[from][to];
if (newPrice < minCosts[to]) {
minCosts[to] = newPrice;
}
}
}
}
return (remain == 0)? maxPrice : -1;
}
}


### Bellman-Ford算法

Bellman-Ford也带有动态规划的思想，而且是非常规整的自底向上的动态规划。它的基本思想是：

    1
1 / \ 3
/   \
2 --- 3
1


Bellman-Ford算法路子是这样，

1. 先用1->2->3=2松弛掉1->3=100
2. 再利用1->3=100的推论，得到新推论1->2->3->4=3
3. 还是利用1->4=3的推论，继续得到1->2->3->4->5=4
4. 最后根据1->5=4得到1->6=5

#### 代码

class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
int[] disTo = new int[N + 1];
Arrays.fill(disTo, Integer.MAX_VALUE);
disTo[K] = 0;
for (int i = 1; i < N; i++) {
for (int[] edge : times) {
if (disTo[edge[0]] == Integer.MAX_VALUE) continue;
disTo[edge[1]] = Math.min(disTo[edge[1]], disTo[edge[0]] + edge[2]);
}
}
int maxPrice = 0;
for (int i = 1; i <= N; i++) {
if (disTo[i] == Integer.MAX_VALUE) return -1;
maxPrice = Math.max(maxPrice, disTo[i]);
}
return maxPrice;
}
}


### Floyd-Warshall算法

#### 代码

class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
int[][] matrix = new int[N + 1][N + 1];
// initialize maxtrix
for (int[] row : matrix) Arrays.fill(row, Integer.MAX_VALUE);
for (int i = 1; i <= N; i++) matrix[i][i] = 0;
for (int[] flight : times) matrix[flight[0]][flight[1]] = flight[2];
// dp
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int includeK = matrix[i][k] + matrix[k][j];
if (matrix[i][k] != Integer.MAX_VALUE && matrix[k][j] != Integer.MAX_VALUE && matrix[i][j] > includeK) matrix[i][j] = includeK;
}
}
}
int maxPrice = 0;
for (int i = 1; i <= N; i++) {
if (matrix[K][i] == Integer.MAX_VALUE) return -1;
maxPrice = Math.max(maxPrice, matrix[K][i]);
}
return maxPrice;
}
}


### BFS + DP

#### 代码

class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
int[][] timeMatrix = new int[N][N];
for (int i = 0; i < N; i++) Arrays.fill(timeMatrix[i], Integer.MAX_VALUE);
for (int[] time : times) timeMatrix[time[0] - 1][time[1] - 1] = time[2];
List<Integer> level = new ArrayList<>();
for (int i = 0; i < N; i++) {
if (timeMatrix[K - 1][i] != Integer.MAX_VALUE) level.add(i);
}
while (!level.isEmpty()) {
int size = level.size();
for (int i = 0; i < size; i++) {
int from = level.remove(0);
for (int to = 0; to < N; to++) {
if (to == K - 1) continue;
if (timeMatrix[from][to] != Integer.MAX_VALUE) {
if (timeMatrix[K - 1][from] + timeMatrix[from][to] < timeMatrix[K - 1][to]) {
timeMatrix[K - 1][to] = timeMatrix[K - 1][from] + timeMatrix[from][to];
}
}
}
}
}
int maxTime = 0;
for (int i = 0; i < N; i++) {
if (i == K - 1) continue;
if (timeMatrix[K - 1][i] == Integer.MAX_VALUE) return -1;
maxTime = Math.max(maxTime, timeMatrix[K - 1][i]);
}
return maxTime;
}
}