문제
풀이
플로이드 와샬(시간복잡도 : O(V^3) 알고리즘 문제이다. 음의 가중치가 없기에, 다익스트라 알고리즘으로도 풀 수 있는 문제인데, 다익스트라 알고리즘의 시간복잡도는 인접리스트를 사용했을 시 O(ElogV)로 간선(E)가 너무 많다면 시간복잡도에서 불리할 수 있다. 플로이드 와샬은 from에서 to로 곧장 가는 경우와 경유지를 통해 가는 경로들을 비교해서 최저값을 찾는 알고리즘이다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <climits>
#define INF 1e9
using namespace std;
int main(){
int n, m;
scanf("%d", &n);
scanf("%d", &m);
vector<vector<int>> dp(101, vector<int>(101));
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
if(i==j) dp[i][j] = 0;
else dp[i][j] = INF;
}
}
for(int i = 0; i<m; i++){
int from, to, value;
scanf("%d %d %d", &from, &to, &value);
dp[from][to] = min(dp[from][to], value); // 같은 경로에 정점이 여러개가 있을 수 있으니 최저값으로 갱신
}
for(int k = 1; k<=n; k++){
for(int i = 1; i<=n; i++){
for(int j = 1 ; j<=n; j++){
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
}
}
}
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n ;j++){
if(dp[i][j] == INF) printf("0 ");
else printf("%d ", dp[i][j]);
}
printf("\n");
}
}
