관리 메뉴
빙응의 공부 블로그
[Argorithm]다익스트라(Dijkstra) 본문
📝개요
그래프 거리 알고리즘에 대해 알아보자
📝다익스트라
다익스트라 알고리즘은 최단 거리를 구하는 알고리즘이다.
주요 특징은 다음과 같다.
| 기능 | 특징 | 시간복잡도 |
| 출발 노드의 모든 노드 간의 최단 거리 탐색 | 에지는 모두 양수 | O(ElogV) |
📝 다익스트라 핵심 이론
총 5단계로 알아보자.
1. 인접 리스트로 그래프 구현하기
- 다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 클것을 대비해서 인접 리스트로 구현하는 것이 좋다.
- 그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결
V = Integer.parseInt(st.nextToken()); // 정점의 개수
E = Integer.parseInt(st.nextToken()); // 간선의 개수
startVertex = Integer.parseInt(br.readLine()); // 시작 정점
// 인접 리스트 초기화
adjacencyList = new ArrayList<>();
for (int i = 0; i <= V; i++) {
adjacencyList.add(new ArrayList<>());
}
// 간선 정보 입력
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
adjacencyList.get(u).add(new Node(v, w));
}2. 최단 거리 배열 초기화하기
최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화한다.
// 거리 배열 및 방문 배열 초기화
distances = new int[V + 1];
Arrays.fill(distances, Integer.MAX_VALUE); // 거리 배열 초기화
distances[startVertex] = 0;
visited = new boolean[V + 1];3. 값이 가장 작은 노드 고르기
최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다. 여기서는 값이 0인 출발 노드에서 시작하면 된다.
4. 최단 거리 배열 업데이트하기
선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다. 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다.
5. 과정 3~4를 반복해서 최단 거리 배열 완성
모든 노드가 처리될 때까지 과정을 반복한다. 과정 4에서 선택 노드가 될때마다 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 대까지 반복하면 된다.
private static void dijkstra() {
// 우선순위 큐를 사용하여 최단 거리 노드를 효율적으로 선택
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 정점을 우선순위 큐에 추가 (거리 0으로 시작)
pq.offer(new Node(startVertex, 0));
while (!pq.isEmpty()) {
Node currentNode = pq.poll();
int u = currentNode.destination;
if (visited[u])
continue;
visited[u] = true;
// 현재 노드와 인접한 모든 노드에 대해
for (Node neighbor : adjacencyList.get(u)) {
int v = neighbor.destination; // 인접 노드
int weight = neighbor.weight; // 간선의 가중치
// 현재 노드를 통해 인접 노드로 가는 경로가 더 짧은지 확인
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
pq.offer(new Node(v, distances[v]));
}
}
}
}
📝[BOJ G4]1753번 최단경로
최단경로 성공
시간 제한메모리 제한제출정답맞힌 사람정답 비율
| 1 초 | 256 MB | 217180 | 66152 | 33844 | 25.754% |
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
예제 입력 1 복사
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
예제 출력 1 복사
0
2
3
7
INF
import java.io.*;
import java.util.*;
public class Main {
static class Node implements Comparable<Node> {
int destination;
int weight;
Node(int destination, int weight) {
this.destination = destination;
this.weight = weight;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.weight, other.weight);
}
}
private static int V, E;
private static List<List<Node>> adjacencyList;
private static int[] distances;
private static boolean[] visited;
private static int startVertex;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // 정점의 개수
E = Integer.parseInt(st.nextToken()); // 간선의 개수
startVertex = Integer.parseInt(br.readLine()); // 시작 정점
// 인접 리스트 초기화
adjacencyList = new ArrayList<>();
for (int i = 0; i <= V; i++) {
adjacencyList.add(new ArrayList<>());
}
// 간선 정보 입력
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
adjacencyList.get(u).add(new Node(v, w));
}
// 거리 배열 및 방문 배열 초기화
distances = new int[V + 1];
Arrays.fill(distances, Integer.MAX_VALUE); // 거리 배열 초기화
distances[startVertex] = 0;
visited = new boolean[V + 1];
// 다익스트라 알고리즘 수행
dijkstra();
// 결과 출력
for (int i = 1; i <= V; i++) {
if (distances[i] == Integer.MAX_VALUE) {
System.out.println("INF");
} else {
System.out.println(distances[i]);
}
}
}
// 다익스트라 알고리즘을 수행하는 스태틱 메소드
private static void dijkstra() {
// 우선순위 큐를 사용하여 최단 거리 노드를 효율적으로 선택
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 정점을 우선순위 큐에 추가 (거리 0으로 시작)
pq.offer(new Node(startVertex, 0));
// 우선순위 큐가 비어있지 않을 때까지 반복
while (!pq.isEmpty()) {
// 큐에서 가장 작은 거리의 노드를 꺼냄
Node currentNode = pq.poll();
int u = currentNode.destination;
// 이미 방문한 노드는 무시
if (visited[u])
continue;
visited[u] = true;
// 현재 노드와 인접한 모든 노드에 대해
for (Node neighbor : adjacencyList.get(u)) {
int v = neighbor.destination; // 인접 노드
int weight = neighbor.weight; // 간선의 가중치
// 현재 노드를 통해 인접 노드로 가는 경로가 더 짧은지 확인
if (distances[u] + weight < distances[v]) {
// 더 짧은 경로가 발견되면 거리 배열을 업데이트
distances[v] = distances[u] + weight;
// 업데이트된 경로를 우선순위 큐에 추가
pq.offer(new Node(v, distances[v]));
}
}
}
}
}
'Argorithm 이론' 카테고리의 다른 글
| [Argorithm]슬라이딩 윈도우 (3) | 2024.11.15 |
|---|---|
| [Argorithm]조합 (0) | 2024.08.20 |
| [Argorithm] 0-1 BFS (0) | 2024.07.24 |
| [Arogorithm]그래프 - 플로이드워셜 (0) | 2024.07.19 |
| [Argorithm]탐색 알고리즘 (1) | 2024.07.14 |
'Argorithm 이론' Related Articles
more
