반응형
정의
- 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘
동작
- 그리디 + 동적 계획법
- 방문하지 않은 노드 중에서 가장 비용이 작은 노드를 선택(Greedy)
- 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신(DP)
초기의 Dijkstra 알고리즘
- 거리 테이블을 매번 탐색하는 순차 탐색 방식
- 최악의 경우 모든 노드들을 확인해야 함 → 이것을 V번 반복
- 시간복잡도 $$O(V^2)$$
- 방문 여부를 체크할 배열
- 각 노드까지의 최소 비용을 저장할 배열
- 미 방문한 노드는 무한한 값으로 초기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class DijkstraTable {
static class Node {
int idx; // 도착 정점
int cost; // 도착 정점으로 가는 비용
public Node(int idx, int cost){
this.idx = idx;
this.cost = cost;
}
}
static final int INFINITE = Integer.MAX_VALUE; // 무한대 값
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int V, E; // 정점과 간선의 개수
static int start; // 출발 지점
static ArrayList<Node>[] graph; // 인접 리스트
static boolean[] visited; // 정점 방문 여부 확인을 위한 재열
static int[] distance; // 출발 정점부터 도착 정점까지의 최소 거리를 저장하기 위한 배열
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
start = Integer.parseInt(br.readLine());
initGraph(); // 그래프 초기화
makeGraph(); // 그래프 생성
dijkstra(); // 다익스트라 알고리즘 실행
printResult(); // 출발 정점에서 각 정점으로 이동 시의 최소 비용 출력
br.close();
}
// 그래프 초기화
static void initGraph(){
graph = new ArrayList[V + 1]; // 정점의 idx는 1 ~ V + 1번까지
for (int i = 1; i < V + 1; i++) {
graph[i] = new ArrayList<>();
}
}
static void makeGraph() throws IOException {
// 그래프 생성
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[from].add(new Node(to, cost));
}
}
static void dijkstra(){
visited = new boolean[V + 1];
distance = new int[V + 1];
// 최소 거리 정보를 담을 배열 초기화 -> 무한한 값으로
Arrays.fill(distance, INFINITE);
distance[start] = 0; // 출발 지점은 0으로 초기화
// 다익스트라 알고리즘
// 모든 정점을 방문했다면 종료 (정점의 개수만큼 반복)
for (int v = 1; v < V + 1; v++) {
int minCost = INFINITE;
int minIdx = -1;
// 현재 정점에서의 거리 비용이 최소인 정점을 선택
for (int i = 1; i < V + 1; i++) {
if (!visited[i] && distance[i] < minCost){
minCost = distance[i];
minIdx = i;
}
}
// 그래프가 끊어진 경우
if (minIdx == -1){
break;
}
// 최종적으로 선택된 정점을 방문처리
visited[minIdx] = true;
// 선택된 정점을 기준으로 인접한 정점의 최소 거리 값을 갱신
for (Node node : graph[minIdx]){
// 인접 정점이 현재 가지는 최소 비용 VS 현재 선택된 정점의 비용 + 현재 선택된 정점에서 인접 정점으로 가는 비용
if (distance[node.idx] > distance[minIdx] + node.cost){
distance[node.idx] = distance[minIdx] + node.cost;
}
}
}
}
static void printResult(){
for (int i = 1; i < distance.length; i++) {
sb.append(distance[i] == INFINITE ? "INF" : distance[i]).append("\\n");
}
System.out.println(sb);
}
}
우선순위 큐를 이용한 Dijkstra 알고리즘
- 기본적인 다익스트라 알고리즘
- 최소 비용을 갖는 노드를 선택 → 주변 노드의 값을 갱신
- 비용을 나타내는 배열에서 갱신된 노드를 제외하고는 무한한 값을 가지게 됨
- 그런 애들을 고려할 필요가 있을까?
- 갱신하는 주변 노드의 값에 대해서만 다음 최소 비용을 갖는 노드를 선택하면 됨
- 삽입연산
- 우선순위 큐에 삽입하는 최대 횟수는 간선의 개수 → O(ELogE)
- 희소 그래프(간선이 얼마 없는 그래프)의 경우 E <= V^2 → O(ElogV)
- 추출연산
- 최대 V개의 노드에 대하여 우선순위 큐에서 추출 → O(VlogV)
- 그러나 모든 인접 노드들을 우선순위 큐에 넣는다면 O(VlogV)를 보장하지 못함
- 최적의 알고리즘 구현을 위해서는 중복되는 노드들을 방문하지 않도록 조건을 넣어줘야 함
- 시간복잡도 $$O((E+V)logV)$$
package com.ssafy.algorithm.mst;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class DijkstraPQ {
// 우선순위 큐 사용을 위한 Comparable 인터페이스 구현
static class Node implements Comparable<Node> {
int idx; // 도착 정점
int cost; // 도착 정점으로 가는 비용
public Node(int idx, int cost){
this.idx = idx;
this.cost = cost;
}
@Override
public int compareTo(Node other) {
// 비용이 작을 수록 높은 우선순위
return Integer.compare(this.cost, other.cost);
}
}
static final int INFINITE = Integer.MAX_VALUE; // 무한대 값
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int V, E; // 정점과 간선의 개수
static int start; // 출발 지점
static ArrayList<Node>[] graph; // 인접 리스트
static PriorityQueue<Node> pq = new PriorityQueue<>();
static int[] distance; // 출발 정점부터 도착 정점까지의 최소 거리를 저장하기 위한 배열
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
start = Integer.parseInt(br.readLine());
initGraph(); // 그래프 초기화
makeGraph(); // 그래프 생성
dijkstra(); // 다익스트라 알고리즘 실행
printResult(); // 출발 정점에서 각 정점으로 이동 시의 최소 비용 출력
br.close();
}
// 그래프 초기화
static void initGraph(){
graph = new ArrayList[V + 1]; // 정점의 idx는 1 ~ V + 1번까지
for (int i = 1; i < V + 1; i++) {
graph[i] = new ArrayList<>();
}
}
static void makeGraph() throws IOException {
// 그래프 생성
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[from].add(new Node(to, cost));
}
}
static void dijkstra(){
distance = new int[V + 1];
// 최소 거리 정보를 담을 배열 초기화 -> 무한한 값으로
Arrays.fill(distance, INFINITE);
distance[start] = 0; // 출발 지점은 0으로 초기화
// 시작 정점에서 시작 정점으로 가는 최소 비용은 0
pq.offer(new Node(start, 0));
// 다익스트라 알고리즘
while (!pq.isEmpty()) {
Node minNode = pq.poll(); // 우선순위 큐에서 poll한 노드 -> 현재 최소 비용을 갖는 정점
// 해당 정점의 비용이 distance 배열에 저장된 값보다 크다면 고려할 필요없음
// 이 코드가 있어야 중복 방문을 막을 수 있음
if (distance[minNode.idx] < minNode.cost) {
continue;
}
// 선택된 정점의 모든 인접 정점들을 탐색
for (Node node : graph[minNode.idx]){
// 간선으로 연결된 정점들을 모두 우선순위 큐에 넣어준다면 중복 발생
// 인접 정점으로의 distance 값과 현재 선택된 정점에서 인접 정점으로 가는 비용을 비교
if (distance[node.idx] > minNode.cost + node.cost){
distance[node.idx] = minNode.cost + node.cost;
pq.offer(new Node(node.idx, distance[node.idx]));
}
}
}
}
static void printResult(){
for (int i = 1; i < distance.length; i++) {
sb.append(distance[i] == INFINITE ? "INF" : distance[i]).append("\\n");
}
System.out.println(sb);
}
}