Algorithm
[GDG 스터디] 다익스트라를 이용하여 모든 노드에 대한 최단 경로 구하기
Uykm
2024. 11. 19. 17:16
다익스트라 알고리즘
다익스트라(Dijkstra) ?
- 다익스트라 알고리즘은 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다.
- 해당 노드까지의 최단 경로를 찾는 과정에서 다른 모든 정점까지의 경로값도 계산해주면서 각 정점까지의 최단 경로도 모두 찾게 된다 !
- 가중치가 양수일 때만 사용 가능하다 !
💡 다익스트라 핵심 개념 - Greedy
- 다익스트라는 그리디(Greedy) 알고리즘의 일종으로, 매 단계마다 **가장 최적의 선택(현재 최단 거리를 가진 정점)**을 한다. → 즉, 아직 방문하지 않은 정점 중에서 최단 거리의 정점을 선택해 탐색한다.
<aside> 💡
방문 여부도 체크해야 하나 ?
- 따로 체크할 필요가 없다 ! → 노드는 한 번 방문했을 때 최단 거리값으로 갱신되기 때문에, 아래처럼 거리를 갱신하는 조건문에 걸리지 않아 우선순위 큐에 이후 방문할 노드로 추가될 일이 없다 !
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.add(new Edge(neighbor, newDist));
}
</aside>
💡 다익스트라 핵심 개념 - 최단 거리 테이블
- 다익스트라 알고리즘의 최단거리 테이블은 특정 시작 정점에서 모든 다른 정점까지의 최단 거리를 기록하는 테이블이다. → 다익스트라 알고리즘이 실행되는 동안 최단 거리를 점진적으로 갱신하면서 경로를 탐색할 때 사용된다.
최단 거리 테이블의 구성과 갱신 과정
- 초기화
- 시작 정점에서의 거리는 0으로 설정한다.
- 나머지 모든 정점은 아직 방문되지 않았으므로 거리를 무한대(∞; INF)로 설정한다.
- 탐색 과정
- 현재 테이블에 있는 최단 거리가 가장 작은 정점을 선택하여 해당 정점을 방문 처리한다.
- 선택된 정점을 기준으로 인접한 정점들을 확인하며, 최단 거리 테이블을 갱신한다.
- 이 과정을 모든 정점을 방문할 때까지 반복한다.
- 결과
- 시작 정점에서 모든 정점까지의 최단 거리를 나타내게 된다.
💡 다익스트라 핵심 개념 - 시간 복잡도 & Heap
- 다익스트라 알고리즘에서 최단 거리를 찾기 위해 선형 검색을 해버리면 시간 복잡도는 O(V^2)가 돼버린다. → 모든 정점에 대해 최단 거리를 갱신하는 과정에서 비효율적인 검색이 발생한다.
<aside> 💡
힙(Heap) 자료구조를 사용하는 이유 !
- 다익스트라 알고리즘에서는 “현재까지 가장 작은 거리”를 가진 정점을 빠르게 선택해야 하기 때문에, 이 과정에서 효율적으로 탐색을 하기 위해 우선순위 큐가 필요한 것이다 ! → 이런 우선순위 큐의 삽입 및 최소값 추출을 효율적으로 할 수 있도록 설계되어 있는 것이 힙 자료구조이다. ( ex: 이진 힙 → 삽입 및 삭제 연산이 O(log V)의 시간 복잡도를 가진다. )
- 우선순위 큐를 구현할 때 힙(Heap) 자료구조를 사용하면 시간 복잡도를 크게 줄일 수 있다. → 주로 이진 힙(Binary Heap)이나 피보나치 힙(Fibonacci Heap)이 사용된다.
- 힙을 사용한 구현에서 시간 복잡도는 O(E * log V)이다. </aside>
💡 다익스트라 핵심 개념 - Priority Queue
- 우선순위 큐(Priority Queue)를 통해 현재 최단 거리를 가진 정점을 빠르게 선택할 수 있다. → **PriorityQueue**는 내부적으로 이진 힙(Binary Heap)을 기반으로 동작한다 !
import java.util.*;
class Graph {
static class Edge {
int target, weight;
Edge(int target, int weight) {
this.target = target;
this.weight = weight;
}
}
private final List<List<Edge>> adjList;
Graph(int nodes) {
adjList = new ArrayList<>();
for (int i = 0; i < nodes; i++) {
adjList.add(new ArrayList<>());
}
}
void addEdge(int source, int target, int weight) {
adjList.get(source).add(new Edge(target, weight));
adjList.get(target).add(new Edge(source, weight)); // For undirected graph
}
void dijkstra(int start) {
int nodes = adjList.size();
int[] distances = new int[nodes];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[start] = 0;
PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
pq.add(new Edge(start, 0));
while (!pq.isEmpty()) {
Edge current = pq.poll();
int currentNode = current.target;
for (Edge edge : adjList.get(currentNode)) {
int neighbor = edge.target;
int newDist = distances[currentNode] + edge.weight;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.add(new Edge(neighbor, newDist));
}
}
}
}
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 2);
graph.addEdge(1, 2, 5);
graph.addEdge(1, 3, 10);
graph.addEdge(2, 4, 3);
graph.addEdge(4, 3, 4);
graph.addEdge(3, 5, 11);
graph.dijkstra(0);
}
}
문제: 최단경로 (백준 1753)
문제 링크
알고리즘 [접근 방법]
- 다익스트라 알고리즘을 이용해서 시작 정점으로부터 각 정점들의 최단 경로를 구해준다.
해결 코드
- 우선순위 큐에 자료가 삽입되고 추출될 때, 거리값이 작은 값이 높은 우선순위에 배정되도록 재정의해줬다.
- 현재 방문한 노드와 인접한 노드들을 탐색하고, 최단 거리 테이블(distances 배열)을 기반으로 시작 노드로부터 해당 노드들까지의 거리를 더 작은 값으로 갱신해주는 과정을 반복한 것이다. → 방문 순서는 현재 노드에서 거리값이 가장 작은 노드들 먼저 방문(우선순위 큐 pr에서 추출)한다.
import java.util.*;
import java.io.*;
public class Main {
static final int INF = Integer.MAX_VALUE;
static int V, E, K;
static int[] distances;
static ArrayList<Node>[] graph;
static boolean[] visited;
static class Node implements Comparable<Node> {
int end;
int distance;
public Node(int end, int distance) {
this.end = end;
this.distance = distance;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.distance, other.distance);
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // 정점 개수
E = Integer.parseInt(st.nextToken()); // 간선 개수
K = Integer.parseInt(br.readLine()); // 시작 노드
visited = new boolean[V + 1];
distances = new int[V + 1];
graph = new ArrayList[V + 1];
for (int i = 1; i <= V; ++i) {
distances[i] = INF;
graph[i] = new ArrayList<>();
}
for (int i = 1; i <= E; ++i) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int distance = Integer.parseInt(st.nextToken());
graph[start].add(new Node(end, distance));
}
dijkstra();
for (int i = 1; i <= V; ++i) {
System.out.println(distances[i] == INF ? "INF" : distances[i]);
}
}
private static void dijkstra() {
distances[K] = 0;
PriorityQueue<Node> queue = new PriorityQueue<>();
// PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> Integer.compare(a.distance, b.distance));
queue.add(new Node(K, 0));
while (!queue.isEmpty()) {
Node cur = queue.poll();
int curNode = cur.end;
int curDistance = cur.distance;
// 처음 노드에서 해당 노드까지의 거리가 갱신될 필요없는 경우
if (curDistance > distances[curNode]) {
continue;
}
// 현재 정점과 연결된 모든 정점을 탐색
for (Node node : graph[curNode]) {
int newNode = node.end;
int newDistance = curDistance + node.distance; // 새로운 거리 계산
// 새로 계산한 거리가 기존 거리보다 작으면 거리 갱신
if (newDistance < distances[newNode]) {
distances[newNode] = newDistance;
queue.add(new Node(newNode, newDistance)); // 갱신된 거리를 큐에 추가
}
}
}
}
}
정리
- 다익스트라 알고리즘은 이진 힙으로 구현된 우선순위 큐를 기반으로 동작하는 알고리즘으로, 가중치가 양수인 (무)방향 그래프에서 사용해야 한다 !
https://thin-azimuth-2a9.notion.site/GDG-144f4ee21c008026a35cc4203db63fa1?pvs=4