Geeksforgeeks - Dijkstra 알고리즘
https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/#algo1
Top 10 algorithms in Interview Questions - GeeksforGeeks
Top 10 algorithms in Interview Questions
www.geeksforgeeks.org
매번 문제를 풀 때 마다 한 번씩 실수하는 알고리즘들을, 다시 한 번 구현해보며 각각을 정리하고 있다.
BFS와 DFS는 어렵지 않게 구현해서 따로 작성하지는 않았지만, 다익스트라는 헤맸던 부분이 생겨 정리하게 되었다.
BFS, DFS와 Dijkstra의 차이점은, 다음 노드로 가기위한 가중치이다.
BFS, DFS -> 다음 노드로 가기위한 가중치는 모두 같음
Dijkstra -> 다음 노드로 가기위한 가중치가 노드간 edge의 value에 따라 다름 (ex : 길 찾기)
따라서 BFS와 DFS는 차례대로 노드들을 방문한다고 하면, Dijkstra는 최소 거리를 가지고 있는 노드부터 탐색을 진행한다.
보통 Source 노드를 정하고, 해당 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 형태로 구현하게 된다.
오늘 헤맸던 점은, 다음으로 방문 할 노드를 정하기위해 "최소 거리를 갖고 있는 노드"를 Queue에 넣은것이 아닌 "최소 거리를 갖고 있는 간선"을 넣는 실수를 했다.
예시
Input:
V = 3, E = 3
u = 0, v = 1, w = 1
u = 1, v = 2, w = 3
u = 0, v = 2, w = 6
adj = {{{1, 1}, {2, 6}}, {{2, 3}, {0, 1}}, {{1, 3}, {0, 6}}}
S = 2
Output:
4 3 0
Explanation:
위의 예시에서도, 가능한 간선들 중 가장 짧은 간선을 선택해도 답이 나오게 된다.
차례대로 알고리즘의 동작을 써보면,
source로부터 각각의 노드 까지의 최단 거리가 담긴 배열 arr과, 각 노드들의 방문 상태를 기록하기위해 노드들의 개수만큼의 크기를 가진 boolean 배열 visited가 있다고 가정하자.
1. source -> source의 거리는 0이므로, arr[source]에 0을 넣어준다.
2. 다익스트라 알고리즘에서는, 아직 최단거리가 구해지지 않은 노드는 해당 노드까지의 거리를 알 수 없다는 표현으로 무한대 값을 집어넣는다. 나는 간단하게 Integer.MAX_VALUE 매크로 변수를 이용해 int 최댓값을 넣어두었다.
3. 가장 작은 최단거리를 갖고 있는 노드를 선택한 후, 해당 노드와 연결된 모든 노드들을 방문하면서 최단 거리를 갱신한다. 갱신 할 때 마다, 해당 노드들을 Priority Queue에 집어넣는다.(다음 분기가 진행될 노드를 선택하기 위함).
4. Priority Queue에서 노드를 빼낸다.(최소 거리를 가진 노드가 선택됨)
5. 3번과 같이 해당 노드와 연결된 모든 노드들을 방문하며 최단 거리를 갱신한다.
분기마다 차례대로 arr의 상태를 써보면,
1. arr = [MAX, MAX, 0]
2. arr[2]가 최단 거리를 가진 노드이므로, 2번 노드를 선택.
2번 노드와 연결된 노드들과의 거리를 구해 최단 거리를 갱신한다.
2 -> 0 = 6
arr[0]의 값은 MAX. 6은 MAX보다 작으므로 arr[0]의 값이 6으로 대체됨. arr[6, MAX, 0]
Priority Queue에 ArrayList (0, arr[0])을 집어넣는다. (Node, value)
2 -> 1 = 3
arr[1]의 값은 MAX. 3은 MAX보다 작으므로 arr[1]의 값이 1로 대체됨. arr[6, 1, 0]
Priority Queue에 ArrayList (1, arr[1])을 집어넣는다. (Node, value)
2번 노드에 관해 탐색이 끝났으므로, visited[2] = true로 만든다.
arr[6, 1, 0]
3. Priority Queue에서 노드를 꺼낸다. (최소 거리를 가진 노드)
queue = ((1, 3), (0, 6)) 인 상태이므로 (1, 3)이 빠진다.
1번 노드가 선택되었으므로, 연결된 모든 노드들을 다시 방문해 최단 거리를 갱신한다.
1 -> 2 = 3 이지만, visited[2]가 true이므로 갱신하지 않는다.
1 -> 0 = 1이다. arr[0]은 6인 상태인데, 새로운 최단 거리가 등장했으므로 갱신한다.
arr[0] : 6 , arr[1] + 1 : 4
6 > 4, arr[0]에 4를 넣어줌.
Priority Queue에 ArrayList (0, arr[0])를 집어넣는다.
1번 노드에 관해 탐색이 끝났으므로, visited[1] = true로 만든다.
arr[4, 1, 0]
4. Queue에서 노드를 꺼낸다. (0, 4)가 빠지는데, 0과 연결된 모든 노드들의 visited 값이 true이므로, 탐색을 종료한다.
++ 추가적인 부분
최소 거리를 가진 노드를 매번 빠르게 꺼내기 위해, 우선순위 큐를 사용했다. ArrayList간의 대소를 비교해야 하므로 (노드, 최단 거리) Comparator를 재정의해서 사용했다.
원래 아래와 같은 형태로 재정의해서 사용해야하지만,
public static Comparator<ArrayList<Integer>> comp1 = new Comparator<>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
if (o1.get(1) > o2.get(1)) return 1;
else if (o1.get(1) == o2.get(1)) return 0;
else return -1;
}
};
Comparator.comparing 메소드와 lambda를 사용해 한 줄로 쓸 수 있다.
public static Comparator<ArrayList<Integer>> comp = Comparator.comparing(o -> o.get(1));
전체 코드
class Solution
{
//Function to find the shortest distance of all the vertices
//from the source vertex S.
static ArrayList<ArrayList<ArrayList<Integer>>> r_adj;
static boolean[] visited;
static int[] ret_arr;
static int answer;
public static Comparator<ArrayList<Integer>> comp = Comparator.comparing(o -> o.get(1));
public static void make_sol(int S) {
PriorityQueue<ArrayList<Integer>> queue = new PriorityQueue<>(comp1);
for (ArrayList<Integer> elem : r_adj.get(S)) {
queue.add(elem);
ret_arr[elem.get(0)] = elem.get(1);
}
visited[S] = true;
ret_arr[S] = 0;
while (!queue.isEmpty()) {
ArrayList<Integer> edge = queue.poll();
int vtx = edge.get(0);
if (!visited[vtx]) {
for (ArrayList<Integer> elem : r_adj.get(vtx)) {
int n_vtx = elem.get(0);
int dist = elem.get(1);
if (ret_arr[n_vtx] > ret_arr[vtx] + dist) {
ret_arr[n_vtx] = ret_arr[vtx] + dist;
}
if (!visited[n_vtx]) {
queue.add(new ArrayList<>((
Arrays.asList(n_vtx, ret_arr[n_vtx])
))); // 실수한 부분. 이전 코드에서는 queue.add(elem);
}
}
visited[vtx] = true;
}
}
}
static int[] dijkstra(int V, ArrayList<ArrayList<ArrayList<Integer>>> adj, int S)
{
// Write your code here
r_adj = adj;
ret_arr = new int[V];
Arrays.fill(ret_arr, Integer.MAX_VALUE);
visited = new boolean[V];
make_sol(S);
return ret_arr;
}
}