아래와 같이 다른 다익스트라 문제와 동일하게 풀었는데 메모리 초과 및 시간초과가 나왔다.
인접 행렬로 풀면 V==20000일 때 인접행렬은 4억개이고 정수형이니 각 크기가 8B면 3200 MB가 되어서 그렇다고 함,,,
import java.util.*;
public class Main {
public static long MAX = 20000 * 300000 * 10 + 1;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int e = in.nextInt();
int startPoint = in.nextInt();
long mat[][] = new long[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(mat[i], MAX);
}
for (int i = 0; i < e; i++) {
int start = in.nextInt();
int end = in.nextInt();
long weight = in.nextLong();
mat[start][end] = Math.min(mat[start][end], weight);
}
long dist[] = dijkstra(startPoint, n, mat);
for (int i = 1; i <= n; i++) {
if (dist[i] >= MAX) {
System.out.println("INF");
} else {
System.out.println(dist[i]);
}
}
}
public static long[] dijkstra(int startPoint, int n, long mat[][]) {
long[] dist = new long[n + 1];
boolean[] isVisited = new boolean[n + 1];
Arrays.fill(dist, MAX);
for (int i = 1; i <= n; i++) {
dist[i] = mat[startPoint][i];
}
dist[startPoint] = 0;
isVisited[startPoint] = true;
for (int i = 1; i < n; i++) {
int index = -1;
long min = MAX;
for (int j = 1; j <= n; j++) {
if (min > dist[j] && !isVisited[j]) {
min = dist[j];
index = j;
}
}
if (index == -1) {
break;
}
isVisited[index] = true;
for (int j = 1; j <= n; j++) {
if (dist[j] > dist[index] + mat[index][j]) {
dist[j] = dist[index] + mat[index][j];
}
}
}
return dist;
}
}
그리고 V<=20000이기 때문에 시간복잡도 O(V^2)로는 4억(약 4초)가 걸린다.
다익스트라 알고리즘을 구하는 순서를 다시 보면 아래와 같다.
- 체크되어 있지 않은 정점 중에서 D의 값이 가장 작은 정점 index 를 선택한다. : O(V)
- index틑 체크한다.
- index와 연결된 모든 정점에 대해 최단거리 갱신: 인접행렬의 경우 O(V^2), 인접리스트의 경우 O(V+E)
여기서 시간을 줄일 수 있는 부분은 1번이다.
(정점 번호, Dist)값을 heap이나 priorityQueue에 넣어서 가장 작은 정점을 선택할 수 있도록 한다.
이떄 시간복잡도는 모든 간선이 들어가는 것이나 마찬가지이다.
왜냐면 dist배열이 업데이트 될때마다 들어가는데, 업데이트 된다는 것의 의미는
어떤 정점에 연결되어 있는 간선에 대해 비교를 한 것과 같다.
따라서 O(ElogE), 즉 (정점 번호, Dist)쌍이 E번 들어갔다가 나오는 시간이 걸린다.
위 풀이를 적용하여 다시 문제를 풀어볼 예정