데이크스트라(다익스트라) 알고리즘 - Dijkstra algorithm
다이나믹프로그래밍기법을 사용한 알고리즘 기법 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다.
특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
특징
1. 현재 노드에서 다른 노드로 가는 최단 거리( 가중치는 음의 간선을 포함하지 않는 양수만 가짐)
2. (현재노드까지 비용 + 다음 노드로 가는 비용) < (다음 노드로 가는 기존 비용) 이라면 갱신
3. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.
구체적인 동작 과정
1. 출발 노드 설정
2. 출발 노드 기준 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드
4. 해당 노드를 거쳐 다른 노드로 가는 경우를 고려하여 최소 비용 갱신
5. 3~4번 과정 반복
BOJ 예시 - 1753 최단 경로 골드4
1753 문제는 주어진 노드에서 다른 노드로 갈 수 있는 최단 경로를 구하는 것이다.
다익스트라 부분만 보여줌
// 최단 경로 알고리즘 다익스트라(Dijkstra)
private static void dijkstra() {
PriorityQueue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.weight - n2.weight);
// 출발 노드 설정
queue.offer(new Node(start, 0));
boolean[] visit = new boolean[v + 1];
// 출발 노드의 비용은 0으로 설정한다.
value[start] = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
// 방문했다면 넘어가준다.
if(visit[node.idx]) continue;
visit[node.idx] = true;
// 방문하지 않는 노드 중 가장 비용이 적은 노드
for (Node nextNode : list[node.idx]) {
int end = nextNode.idx;
int weight = nextNode.weight;
// 현재 노드 기준 각 노드의 최소 비용을 저장해준다.
if (value[end] > value[node.idx] + weight) {
value[end] = value[node.idx] + weight;
queue.add(new Node(end, value[end]));
}
}
}
}
이렇게 현재 노드에서 갈 수 있는 노드를 찾을 때 선형 탐색을 통해서 방문하지않고 && 최소비용인것을 찾을 수 있지만 우선순위큐를 사용해서 더욱 성능이 좋게 알고리즘을 짤 수 있다.
자세한 알고리즘 풀이 링크
https://akys159357.tistory.com/410
'CS > 알고리즘' 카테고리의 다른 글
Backtracking (1) | 2023.10.24 |
---|---|
Priority Queue (1) | 2023.10.23 |
Stack & Queue 알고리즘 공부 (1) | 2023.10.14 |