You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1. Example 1: Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 Example 2: Input: times = [[1,2,1]], n = 2, k = 1 Output: 1 Example 3: Input: times = [[1,2,1]], n = 2, k = 2 Output: -1 Constraints: 1 <= k <= n <= 100 1 <= times.length <= 6000 times[i].length == 3 1 <= ui, vi <= n ui != vi 0 <= wi <= 100 All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
Bellman-Ford single source shortest path alogithm:
Ttime complexity: O(VE)
class Solution { public int networkDelayTime(int[][] times, int n, int k) { // Step 1: Initialize distances from src to all other // vertices as INFINITE // src will have distance as 0 int[] leastTimes = new int[n + 1]; Arrays.fill(leastTimes, Integer.MAX_VALUE); leastTimes[k] = 0; // Step 2: Relax all edges |V| - 1 times. A simple // shortest path from src to any other vertex can // have at-most |V| - 1 edges for (int i = 1; i< n; i++) { for(int[] time : times) { int u = time[0], v = time[1], w = time[2]; if (leastTimes[u] != Integer.MAX_VALUE && leastTimes[v] > leastTimes[u] + w) { leastTimes[v] = leastTimes[u] + w; } } } // check to see if any of the distances are MAX_VALUE, this will // show that the node was never relaxed so return -1 int delay = 0; for (int i = 1; i< leastTimes.length; i++) { if (leastTimes[i] == Integer.MAX_VALUE) { return -1; } if (leastTimes[i] > delay) { delay = leastTimes[i]; } } return delay; } }
原文：https://www.cnblogs.com/incrediblechangshuo/p/14479963.html