[アルゴリズム]バックアップ-フロイド
スタンダードフロイド
各ノードの仮定によって更新されます.
3重for文を用い,時間複雑度はO(n^3)である.
コンセプトアレンジ
floodとshall:すべての頂点からすべての頂点への最短距離更新アルゴリズム
各ノードの仮定によって更新されます.
3重for文を用い,時間複雑度はO(n^3)である.
説明する
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class baekjoon_11404 {
static int n, m;
static int[][] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
graph = new int[n + 1][n + 1];
for (int i = 0; i < n + 1; i++) {
Arrays.fill(graph[i], Integer.MAX_VALUE);
graph[i][i] = 0;
}
for (int i = 0; i < m; i++) {
String[] inputs = br.readLine().split(" ");
int a = Integer.parseInt(inputs[0]);
int b = Integer.parseInt(inputs[1]);
int c = Integer.parseInt(inputs[2]);
// 경로가 하나가 아닐 수 있다는 조건이 있
graph[a][b] = Math.min(c, graph[a][b]);
}
floyd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][j] == Integer.MAX_VALUE) {
System.out.print(0 + " ");
} else {
System.out.print(graph[i][j] + " ");
}
}
if (i != n) {
System.out.println();
}
}
}
//dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]
private static void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (graph[i][k] == Integer.MAX_VALUE || graph[k][j] == Integer.MAX_VALUE) {
continue;
}
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}
}
Reference
この問題について([アルゴリズム]バックアップ-フロイド), 我々は、より多くの情報をここで見つけました https://velog.io/@injoon2019/알고리즘-백준-플로이드テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol