2020-01-30 22:22:58
问题描述：
问题求解：
解法一：floyd
这个题目一看就是floyd解最合适，因为是要求多源最短路，floyd算法是最合适的，时间复杂度为O(n ^ 3)。
int inf = (int)1e9;
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) Arrays.fill(dp[i], inf);
for (int i = 0; i < n; i++) {
dp[i][i] = 0;
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int d = edge[2];
dp[u][v] = d;
dp[v][u] = d;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] > dp[i][k] + dp[k][j]) {
dp[i][j] = dp[i][k] + dp[k][j];
}
}
}
}
List<int[]> note = new ArrayList<>();
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (dp[i][j] <= distanceThreshold) cnt += 1;
}
note.add(new int[]{i, cnt});
}
Collections.sort(note, new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
return o1[1] == o2[1] ? o2[0] - o1[0] : o1[1] - o2[1];
}
});
return note.get(0)[0];
}
解法二：dijkstra
使用邻接表 + 优先队列可以将单源最短路的时间复杂度降到O(ElogV)，所以整体的时间复杂度为O(VElogV)。
int inf = (int)1e9;
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
int[][] dp = new int[n][n];
List<int[]> note = new ArrayList<>();
List<int[]>[] graph = new List[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int d = edge[2];
graph[u].add(new int[]{v, d});
graph[v].add(new int[]{u, d});
}
for (int i = 0; i < n; i++) {
int[] dist = new int[n];
Arrays.fill(dist, inf);
dist[i] = 0;
dijkstra(graph, i, dist);
int cnt = 0;
for (int j = 0; j < n; j++)
if (dist[j] <= distanceThreshold)
cnt += 1;
note.add(new int[]{i, cnt});
}
Collections.sort(note, new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
return o1[1] == o2[1] ? o2[0] - o1[0] : o1[1] - o2[1];
}
});
return note.get(0)[0];
}
private void dijkstra(List<int[]>[] graph, int node, int[] dist) {
Set<Integer> used = new HashSet<>();
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
for (int[] next : graph[node]) pq.add(next);
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int v = curr[0];
int d = curr[1];
if (used.contains(v)) continue;
used.add(v);
dist[v] = d;
for (int[] next : graph[v]) {
if (dist[next[0]] > dist[v] + next[1]) {
dist[next[0]] = dist[v] + next[1];
pq.add(new int[]{next[0], dist[next[0]]});
}
}
}
}
最短路径 floyd/dijkstra-Find the City With the Smallest Number of Neighbors at a Threshold Distance
原文：https://www.cnblogs.com/hyserendipity/p/12244208.html