출처 : 2021 이코테
최단 경로 문제
- 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다.
- 다양한 문제 상황
- 한 지점에서 다른 한 지점까지의 최단 경로
- 한 지점에서 다른 모든 지점까지의 최단 경로
- 모든 지점에서 다른 모든 지점까지의 최단 경로
- 각 지점은 그래프에서 노드로 표현
- 지점 간 연결된 도로는 그래프에서 간선으로 표현
다익스트라 최단 경로 알고리즘 개요
- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
- 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.
- 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.
- 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.
- 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
다익스트라 최단 경로 알고리즘
- 알고리즘의 동작 과정
- 출발 노드를 설정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3번과 4번을 반복한다.
방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택하는 과정을 반복할때마다, 선택된 노드까지의 최단거리는 더이상 바뀌지 않음!
매 상황마다 아직 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는것을 반복함으로써 모든 노드에 대해 방문처리가 끝났을 때, 전체 노드까지의 모든 최단거리를 알 수 있다.
다익스트라 알고리즘의 단순한 형태는 출발 노드로부터 다른 모든 노드까지의 최단거리를 구하는것과 같다.
다익스트라 최단 경로 알고리즘
- 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다.
- 처리 과정에서 더 짧은 경로를 찾으면 '이제부터는 이 경로가 제일 짧은 경로다' 라고 갱신한다.
다익스트라 알고리즘 : 동작 과정 살펴보기
방문하지 않은 노드 중 가장 거리가 짧은 노드를 매번 선택하여 해당 노드를 거쳐가는 경로를 확인하여 위 테이블을 갱신한다.
- 1번 노드를 거쳐갈때의 비용과 현재까지의 비용을 비교하여 더 짧은 노드로 테이블을 갱신할 수 있도록 한다.
1번 노드에서 갈 수 있는 경로는 2, 5, 1 길이의 경로.
2, 3, 4번 노드의 경우 각각 도달하기까지의 거리가 무한이였지만 1번 노드를 거쳐 가게된다면 2, 5, 1 만큼의 거리를 갖게 된다. 이때, 최단거리값이 갱신된다.
4번 노드를 거쳐갈때의 노드를 확인하기 위해서, 4번 노드와 인접한 노드를 확인한다.
다익스트라 알고리즘이 그리디한 방법으로 동작할 수 있는 방법은 최단거리의 노드를 고를 때 마다, 해당 노드까지의 거리는 더이상 바뀌지 않기 때문이다.
다시말해, 4번 노드까지 도착하기위한 최단거리는 1이기때문에 이와같이 4번 노드를 거쳐갈때를 고려할때는 4번노드까지의 비용인 1에 4번노드에서 3번노드까지 가기위한 비용인 3을 더하면 된다.
위의 표를 보면 3번노드까지의 최단거리값이 5라고 되어있었지만, 4번노드를 거쳐갈때의 최단거리값이 1+3으로 더 작기때문에 더 작은값으로 갱신한다.
마찬가지로 5번노드까지 최단거리는 이전까지는 무한이였는데, 4번노드를 거쳐갈때의 경로를 확인해봤더니 1+1으로 갱신!
다음단계로 방문하지 않은 노드 중 최단거리가 가장 작은 노드를 선택해야하는데, 2번노드와 5번노드가 같은 비용을 갖고 있으므로 어떤 노드를 선택해도 상관없지만, 일반적으로는 더 낮은 번호를 가진 노드를 선택한다.
2번노드를 거쳐가는 두가지 경우를 확인할 수 있다. 각각 3번노드로 가는 길이 3의 길, 4번 노드로 가는 길이 2의 길.
그리고 2까지의 최단거리가 2 이기때문에, 2를 거쳐 노드 3과 4로 가는 거리는 2+3, 2+2가 되게 된다.
근데, 현재 노드 3과 4로 가는 최단거리가 각각 4와 1로 5와 4보다 작으므로 최단거리는 갱신되지 않는다.
이미 방문처리가 된 노드는 무시할 수도 있다. 왜냐하면 그 노드까지의 최단거리값이 이미 결정되어 바뀌지 않기 때문이다.
2번 노드를 방문했으므로, 다음으로 방문하지 않은 노드를 선택하여야하는데 그 다음으로 최단거리값이 가장 작은 5번 노드를 선택한다.
또 마찬가지로 5번 노드를 거쳐가는 경우를 확인하여 5번 노드에서 3번, 6번 노드로 가는 거리를 확인하여 각각의 최단거리값이 갱신될 수 있는지를 확인한다.
먼저 3번 노드까지의 최단거리는 5번노드까지의 최단거리인 2와 5번 노드에서 3번 노드까지의 거리 1, 2+1 3이다.
이전에 3번노드까지의 최단거리가 4였으므로 3으로 갱신된다.
마찬가지로 6번노드같은경우, 아직까지 도착이 불가능한 무한의 값을 갖고있었는데 마찬가지로 2+2인 4로 최단거리가 갱신되는것을 확인할 수 있다.
그다음 거리값이 작은 노드는 3번이므로, 3번 노드를 방문한다.
3번 노드에 대해 마찬가지로 인접한 노드의 정보를 확인해 테이블이 갱신되는지 확인한다.
일단, 2번과 6번 노드 둘다 갱신되지 않음!
마지막 노드에 대한 정보는 굳이 처리하지 않아도 괜찮다. -> 다른 노드까지의 최단거리값은 바뀌지 않으므로
따라서 다익스트라 알고리즘의 경우 마지막 노드는 굳이 처리하지 않아도 전체 결과를 알 수 있다.
위 예제와 같은 경우, 애초에 6번 노드로부터 시작되는 간선이 없으므로 더이상 볼게 없기도 하다.
다익스트라 알고리즘의 특징
- 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정(해당 노드를 거쳐가는 각각의 경우를 확인해서 테이블을 갱신할지 말지 결정하는 과정)을 반복한다.
- 단계를 거치며 한번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
- 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
- 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 더 넣어야 한다.
다익스트라 알고리즘 : 간단한 구현 방법
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색) 한다.
다익스트라 알고리즘 : 간단한 구현 방법 (Python)
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
min_value = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1, n + 1):
if distance[i] < min_value and not visited[i]:
min_value = distance[i]
index = i
return index
def dijkstra(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
visited[start] = True
for j in graph[start]:
distance[j[0]] = j[1]
# 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for i in range(n - 1):
# 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
now = get_smallest_node()
visited[now] = True
# 현재 노드와 연결된 다른 노드를 확인
for j in graph[now]:
cost = distance[now] + j[1]
# 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[j[0]]:
distance[j[0]] = cost
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])
다익스트라 알고리즘 : 간단한 구현 방법 (Java)
자바의 경우, 별도로 튜플과 같은 라이브러리를 제공하지 않으므로 Node 라는 클래스를 만들어 특정 노드 번호까지의 거리가 얼마인지를 정의할 수 있는 하나의 자료구조를 정의한다.
이때 Node는 인접한 노드를 의미하는 하나의 클래스이다.
따라서 Node 인스턴스에 노드와 인접한 노드에 대한 정보를 담는다.
그리고 ArrayList를 중첩하여 사용한다.
import java.util.*;
class Node {
private int index;
private int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
}
public class Main {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
public static int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 방문한 적이 있는지 체크하는 목적의 배열 만들기
public static boolean[] visited = new boolean[100001];
// 최단 거리 테이블 만들기
public static int[] d = new int[100001];
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
public static int getSmallestNode() {
int min_value = INF;
int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
public static void dijkstra(int start) {
// 시작 노드에 대해서 초기화
d[start] = 0;
visited[start] = true;
for (int j = 0; j < graph.get(start).size(); j++) {
d[graph.get(start).get(j).getIndex()] = graph.get(start).get(j).getDistance();
}
// 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
for (int i = 0; i < n - 1; i++) {
// 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
int now = getSmallestNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드를 확인
for (int j = 0; j < graph.get(now).size(); j++) {
int cost = d[now] + graph.get(now).get(j).getDistance();
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph.get(now).get(j).getIndex()]) {
d[graph.get(now).get(j).getIndex()] = cost;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Node>());
}
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph.get(a).add(new Node(b, c));
}
// 최단 거리 테이블을 모두 무한으로 초기화
Arrays.fill(d, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
System.out.println("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(d[i]);
}
}
}
}다익스트라 알고리즘 : 간단한 구현 방법 성능 분석
- 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다.
- 따라서 전체 시간 복잡도는 O(V^2)이다. (V는 노드의 개수)
- 일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5000개 이하라면 이 코드로 문제 해결 가능
- 하지만 노드의 개수가 10,000개가 넘어간다면? -> 1억번 이상 연산이 되므로 시간초과 위험
따라서..
우선순위 큐(Priority Queue)
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조.
- 에를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우에 우선순위 큐를 이용할 수 있다.
- Python, C++, Java를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원
| 자료구조 | 추출되는 데이터 |
| 스택(Stack) | 가장 나중에 삽입된 데이터 |
| 큐(Queue) | 가장 먼저 삽입된 데이터 |
| 우선순위 큐(Priority Queue) | 가장 우선순위가 높은 데이터 |
힙(Heap)
- 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나
- 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다.
최소 힙 : 값이 낮은 데이터부터 꺼내는 방식
최대 힙 : 값이 높은 데이터부터 꺼내는 방식
- 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다.
| 우선순위 | 삽입 시간 | 삭제 시간 |
| 리스트 | O(1) | O(N) |
| 힙(Heap) | O(logN) | O(logN) |
리스트
- 데이터를 삽입할때는 그냥 데이터를 맨 뒤에 넣으면 되서 상수시간
- 데이터를 삽입할때는 전체 데이터를 순회하며 우선순위가 가장 높은 데이터가 뭔지 확인해야하므로 선형시간
힙
- 내부적으로 트리구조로 되어있어 데이터를 삽입하거나 삭제할 때 logN만큼의 수행시간이 걸리게 된다.
힙 라이브러리 사용 예제 : 최소 힙
파이썬 heapq 라이브러리는 기본적으로 최소힙이다. (우선순위가 낮은 원소부터 꺼내진다)
import heapq
#오름차순 힙 정렬(Heap Sort)
def heapsort(iterable) :
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable :
heapq.heappush(h, value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for i in range(len(h)) :
result.append(heapq.heappop(h))
return result
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)
#실행 결과
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]힙 자료구조는 기본적으로 데이터를 넣을 때 O(logN)만큼의 시간이 걸리므로 위와 같이 n개의 데이터를 힙에 넣었다가 꺼내는 과정을 수행하게되면 O(NlogN)만큼 걸리게 된다.
이는 기본적으로 표준 라이브러리에서 제공하는 병합정렬, 퀵정렬 기반의 정렬 알고리즘과 동일한 시간복잡도라고 할 수 있다.
즉 힙 정렬 또한 마찬가지로 힙에 데이터를 넣고 빼는 과정에서 최악의 경우에도 O(NlogN)을 보장한다.
힙 라이브러리 사용 예제 : 최대 힙
import heapq
# 내림차순 힙 정렬(Heap Sort)
def heapsort(iterable) :
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable :
heapq. heappush(h, -value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for i in range(len(h)) :
result.append(-heapq.heappop(h))
return result
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)
#실행 결과
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]데이터를 넣기 전에 데이터의 부호를 바꾸어 넣고, 다시 빼면서 부호를 바꾸어주면 최대 힙을 사용하는것과 같은 효과이다.
다익스트라 알고리즘 : 개선된 구현 방법
- 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙(Heap) 자료구조를 이용한다.
- 다익스트라 알고리즘이 동작하는 기본 원리는 동일하다.
- 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용한다는 점이 다르다.
- 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.
다익스트라 알고리즘 : 동작 과정 살펴보기 (우선순위 큐)
초기 상태는 기존의 다익스트라 알고리즘과 같다.
큐에 데이터를 넣을 때, 튜플 형태로 데이터를 묶어 넣는다. -> (0, 1) : 거리 0 , 노드 1
그럼 이 거리를 기준으로 해서 거리가 작은 원소가 빨리 나오게 된다.
매 단계마다 우선순위 큐에서 원소를 꺼내 해당 노드까지의 거리를 확인한 후 그 노드를 거쳐가는 각각의 경우까지 고려하면 된다.
가장 먼저 우선순위 큐 에서 (0, 1)을 꺼낸다.
이때 노드 1에서 방문처리를 하고, 인접노드에 대해 최단거리를 확인한다.
그리고 최단거리가 갱신된 노드에 대해 우선순위 큐 에 갱신된 값을 넣는다.
그다음 가장 위에 있는 (1, 4)를 꺼내 최단거리를 확인한다.
노드 3과 5의 경우, 갱신이 다 이루어지므로 테이블에 반영해주고 우선순위 큐 에도 갱신된 값을 넣어준다.
그 다음 우선순위를 갖고있는 (2, 2)를 꺼내 인접 노드까지의 최단거리를 확인한다.
3번노드와 4번노드까지의 거리가 모두 최단거리가 아니므로 따로 갱신이 되지 않고, 우선순위 큐에도 튜플이 새로 들어가지 않는다.
그 다음 우선순위인 (2, 5)를 꺼내 확인.
5번노드에서 3번노드와 6번노드까지의 최단거리가 둘다 갱신되므로 테이블을 갱신하고 우선순위 큐 에도 튜플을 삽입한다.
그 다음 원소인 (3, 3)을 꺼내 확인.
인접노드인 2번노드와 6번노드의 최단거리가 둘다 갱신되지 않는다.
다음 원소인 (4, 3)을 꺼내 확인.
3번 노드는 이미 방문한 노드라 무시한다. 이때 방문 여부를 체크하는 테이블을 만들수도 있을 것 같은데, 이렇게 하지 않고 최단거리 테이블과 비교해서 현재 노드 3번의 거리인 3보다 꺼낸 원소의 거리 4가 더 크기때문에 현재 꺼낸 원소를 무시하는 방법을 사용할 수 있다.
3번노드는 이미 처리가 되었기때문에 3번노드까지의 최단거리는 이미 결정되었다.
현재 우선순위큐에서 꺼낸 값이 테이블에 있는 값보다 더 크다면 이미 처리가 된 노드라고 간주할 수 있으므로 다음으로 그냥 넘어가도된다.
6번 노드에서 출발하는 간선이 없으므로 이동할 수 있는 인접노드가 없고 따라서 테이블갱신 및 우선순위 큐 갱신은 되지 않는다.
현재 꺼낸 원소의 거리가 노드번호 3번의 거리 3보다 크므로 무시한다.
다익스트라 알고리즘 : 개선된 구현 방법 (Python)
우선순위 큐를 이용해 코드를 작성.
별도의 방문처리를 체크하는 테이블이 필요하지 않으므로 visited 테이블은 사용하지 않는다.
기존에 존재하던 현재 상황에서 가장 최단거리가 짧은 노드를 선택하는 함수는 더이상 사용되지 않는다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 다익스트라 알고리즘을 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])다익스트라 알고리즘 : 개선된 구현 방법 (Java)
distance가 낮은 값이 더 높은 우선순위를 갖게 하기 위해 comparable 인터페이스를 구성하여 하나의 클래스를 정의.
import java.util.*;
class Node implements Comparable<Node> {
private int index;
private int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
@Override
public int compareTo(Node other) {
if (this.distance < other.distance) {
return -1;
}
return 1;
}
}
public class Main {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
// 노드의 개수는 최대 100,000개라고 가정
public static int n, m, start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 최단 거리 테이블 만들기
public static int[] d = new int[100001];
public static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.offer(new Node(start, 0));
d[start] = 0;
while(!pq.isEmpty()) { // 큐가 비어있지 않다면
// 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
Node node = pq.poll();
int dist = node.getDistance(); // 현재 노드까지의 비용
int now = node.getIndex(); // 현재 노드
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (d[now] < dist) continue;
// 현재 노드와 연결된 다른 인접한 노드들을 확인
for (int i = 0; i < graph.get(now).size(); i++) {
int cost = d[now] + graph.get(now).get(i).getDistance();
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[graph.get(now).get(i).getIndex()]) {
d[graph.get(now).get(i).getIndex()] = cost;
pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
// 그래프 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Node>());
}
// 모든 간선 정보를 입력받기
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph.get(a).add(new Node(b, c));
}
// 최단 거리 테이블을 모두 무한으로 초기화
Arrays.fill(d, INF);
// 다익스트라 알고리즘을 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
System.out.println("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(d[i]);
}
}
}
}다익스트라 알고리즘 : 개선된 구현 방법 성능 분석
- 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이다.
- 노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 V이상의 횟수로는 처리되지 않는다. (이미 방문한 노드는 무시되기 때문!)
- 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총횟수는 최대 간선의 개수(E)만큼 연산이 수행될 수 있다.
- 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.
- 시간 복잡도를 O(ElogE)로 판단할 수 있다.
- 중복 간선을 포함하지 않는 경우에 이를 O(ElogV)로 정리할 수 있다.
- O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)
통상적으로 간선의 개수가 10만개, 노드의 개수가 1만개 이상으로 많아져도 1초 안쪽의 시간으로 출발 노드부터 마지막 노드까지 모든 노드의 최단거리를 구할 수 있다.
플로이드 워셜 알고리즘
- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
- 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.
- 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않는다.
- 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
- 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.
점화식에 맞게 3중 반복문을 이용해서 2차원 테이블을 갱신해주는 방식으로 동작.
실제 알고리즘 구현 난이도는 다익스트라 알고리즘보단 쉬운편!
하지만 모든 노드에서 다른 모든 노드까지의 최단거리를 구하는 과정에서 시간복잡도는 O(n^3)이다.
실제 문제 풀이 과정에서는 노드의 개수가 적은 상황에서 효과적으로 사용할 수 있으며, 노드의 개수나 간선의 개수가 많은 경우엔 일반적으로 다익스트라 알고리즘을 사용하는것이 맞다.
플로이드 워셜 알고리즘의 로직
- 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.
- a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
- 점화식은 다음과 같다.
특정한 노드 k를 거쳐갔을때를 기준으로 해서 테이블을 갱신한다는점은 다익스트라 알고리즘과 유사성이 있다.
다만, 플로이드 워셜 알고리즘은 a에서 b로 가는 도중, k를 거쳐갈때의 거리가 더 짧을때 그 값으로 갱신할 수 있도록 한다.
플로이드 워셜 알고리즘 : 동작 과정 살펴보기
맨 처음에는 각 노드를 기준으로 현재 노드와 인접한 노드들을 기준으로 테이블을 갱신.
각 노드로부터 다른 노드까지의 거리를 테이블에 기록
이후, 1번노드 2번노드 3번노드 4번노드 각각의 노드를 거쳐가는 경로를 확인하여 전체 테이블을 갱신하면된다.
1번 노드를 거쳐 가는 경우를 고려하기때문에 a와 b는 1번 노드를 제외한 2, 3, 4번 노드로 결정된다.
그리고 자기 자신에서 자기 자신으로 가는 중앙 대각선 부분도 제외한다.
따라서, 2, 3, 4를 조합하여(3C2) 6가지의 경우의 수를 만들어 값을 도출해본다.
k라는 변수를 이용해서 모든 노드에 대해 하나씩 확인하며 해당 노드를 거쳐가는 경우에 대해 고려하고, 매번 모든 a와 b에 대해서 점화식을 갱신하기때문에 실제로 구현할땐 3중 반복문을 이용해서 구현할 수 있도록 한다.
플로이드 워셜 알고리즘 (Python)
코드 자체는 다익스트라 알고리즘에 비해 상당히 간결하다.
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용은 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 수행된 결과를 출력
for a in range(1, n + 1):
for b in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if graph[a][b] == 1e9:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()플로이드 워셜 알고리즘 (Java)
보통 노드의 개수는 500개를 넘지 않는다.
import java.util.*;
public class Main {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
// 노드의 개수(N), 간선의 개수(M)
// 노드의 개수는 최대 500개라고 가정
public static int n, m;
// 2차원 배열(그래프 표현)를 만들기
public static int[][] graph = new int[501][501];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 최단 거리 테이블을 모두 무한으로 초기화
for (int i = 0; i < 501; i++) {
Arrays.fill(graph[i], INF);
}
// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (a == b) graph[a][b] = 0;
}
}
// 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for (int i = 0; i < m; i++) {
// A에서 B로 가는 비용은 C라고 설정
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph[a][b] = c;
}
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 수행된 결과를 출력
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (graph[a][b] == INF) {
System.out.print("INFINITY ");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.print(graph[a][b] + " ");
}
}
System.out.println();
}
}
}플로이드 워셜 알고리즘 성능 분석
- 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행한다.
- 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.
- 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.
'ETC > 알고리즘 이론' 카테고리의 다른 글
| [알고리즘] 그리디 알고리즘 ( 탐욕 알고리즘 ) (Python, Java) (0) | 2021.10.19 |
|---|---|
| [알고리즘] 리스트의 모든 조합 구할때 고려할점 (permutations, combinations VS product) (Python) (0) | 2021.08.20 |
| [알고리즘] 경우의 수 (순열, 조합) 구하기 - itertools (Python) (0) | 2021.08.06 |
| [알고리즘] 재귀함수 (Recursive Function) (0) | 2021.08.02 |
| [알고리즘] 피보나치 수열(Fibonacci Sequence) 알고리즘 (JAVA) (0) | 2020.10.16 |
댓글