학습 목표
· 최단 경로(Shortest Path) 알고리즘이란?
· 다익스트라 알고리즘
- 간단한 다익스트라 알고리즘
- 개선된 다익스트라 알고리즘
· 플로이드 워셜 알고리즘
최단 경로(Shortest Path) 알고리즘이란?
· 가장 짧은 경로를 찾는 알고리즘, '길 찾기' 문제로 불린다.
· 문제를 그래프로 표현하고 각 지점을 노드, 지점간 연결된 도로는 간선이라한다.
· 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용된다.
· 다양한 사례가 존재하며, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다.
ex) 한 지점에서 다른 특정 지점까지 최단 경로 구하기, 모든 지점에서 다른 모든 지점까지 최단 경로 구하기 등
다익스트라 알고리즘
· 그래프에 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
· 음의 간선(0보다 작은 값을 가지는 간선)이 없어야 정상적으로 동작
· 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 GPS 소프트웨어의 기본 알고리즘으로 자주 사용된다.
· 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하므로, 그리디 알고리즘으로 분류된다.
다익스트라 알고리즘의 원리
1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산
5. 위 과정에서 3, 4번을 반복
· 각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하여 리스트를 계속 갱신하고,
매번 현재 처리하고 있는 노드를 기준으로 주변을 확인하며,
현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 해당 경로를 제일 짧은 경로로 판단한다.
▶ 예시 - 1번 노드에서 다른 모든 노드로 가는 최단 경로 구하기
· 초기화
출발 노드인 1번 노드에서 다른 노드로의 최단 거리를 표시할 테이블을 생성한다.
초기 상태에서는 다른 모든 노드로 가는 최단 거리를 모두 '무한'으로 초가화한다.
· step 0.
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 출발 노드에서 출발 노드로의 거리는 0이므로 출발 노드가 선택된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
· step 1.
1번 노드를 거쳐 다른 노드로 가는 비용을 계산한다.
2, 4번 노드로 이동하는 비용 2(0 + 2), 5(0 + 5), 1(0 + 1)으로 리스트를 갱신한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
· step 2.
방문하지 않은 노드 중에 최단 거리가 가장 짧은 노드를 선택한다.
4번 노드가 선택되고, 4번 노드를 거쳐 갈 수 있는 노드를 확인한다.
확인된 3, 5번 노드를 4번 노드로 거쳐 가능 비용은 4(1+3), 2(1+1)이다.
두 값이 기존 리스트에 담겨 있는 값보다 작으므로 리스트를 갱신한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
· step 3.
방문하지 않은 노드 중에 최단 거리가 가장 짧은 노드를 선택한다.
2번 노드가 선택되고, 2번 노드를 거쳐 갈 수 있는 노드를 확인한다.
확인된 4, 3번 노드를 2번 노드로 거쳐 가능 비용은 4(2+2), 3(2+3)이다.
현재 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
· step 4.
방문하지 않은 노드 중에 최단 거리가 가장 짧은 노드로 5번 노드가 선택된다.
5번 노드를 거쳐 3, 6번 노드로 가능 비용은 3(2+1), 6(2+2)이다.
두 값이 기존 리스트에 담겨 있는 값보다 작으므로 리스트를 갱신한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
· step 5.
위와 같은 과정을 반복한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
· step 6.
위와 같은 과정을 반복한다. 이때, 모든 노드를 방문했으므로 로직을 종료한다.
1번 노드에서 출발하여 2, 3, 4, 5, 6번 노드까지 가기 위한 최단 경로는 각각 2, 3, 1, 2, 4가 된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
· 선택된 노드는 '최단 거리'가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.
ex) step 2에서 선택된 4번 노드의 최단 경로는 1이고, 이는 step3~step6 이후에도 변함 없다.
· 즉, 다익스트라 알고리즘은 한 단계 당 하나의 노드에 대한 최단 거리를 확실히 찾는다.
다익스트라 알고리즘을 구현하는 두 가지 방법
1. 구현하기 쉽지만 느리게 동작하는 코드 - 시간 복잡도 O(V^2)
2. 구현하기 좀 더 까다롭지만 빠르게 동작하는 코드 - 시간 복잡도 O(ElogV)
간단한 다익스트라 알고리즘
· 다익스트라에 의해 처음 고안되었던 알고리즘
원리
1. 각 노드에 대한 최단 거리를 담는 1차원 리스트 선언
2. 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해, 1차원 리스트의 모든 원소를 확인(순차 탐색)
import java.util.ArrayList;
import java.util.Scanner;
import java.util.stream.IntStream;
/*
입력값
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
*/
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 DijkstraExam {
private static int n;
static int start;
static ArrayList<ArrayList<Node>> graph;
static boolean[] visited;
static int[] distance;
public static void main(String[] arsgs){
Scanner scanner = new Scanner(System.in);
//노드의 개수, 간선의 개수 입력
n = scanner.nextInt();
int m = scanner.nextInt();
//시작 노드 번호 입력
start = scanner.nextInt();
//각 노드에 연결되어 있는 노드에 대한 정보를 담음
graph = new ArrayList<>();
IntStream.range(0,n+1).forEach(i->graph.add(new ArrayList<Node>()));
//방문 여부를 체크하는 배열
visited = new boolean[n+1];
//IntStream.range(0, visited.length).forEach(i->visited[i]=false);
//최단 거리 테이블을 모두 무한으로 초기화
distance = new int[n+1];
IntStream.range(0, distance.length).forEach(i->distance[i]=Integer.MAX_VALUE);
//모든 간선 정보를 입력
IntStream.range(0,m).forEach(i->{
//a번 노드에서 b번 노드로 가는 비용이 c임
int a = scanner.nextInt();
int b = scanner.nextInt();
int c = scanner.nextInt();
graph.get(a).add(new Node(b,c));
});
//다익스트라 알고리즘 수행
dijkstra();
//모든 노드로 가기 위한 최단 거리 출력
IntStream.rangeClosed(1, n).forEach(i->{
if(distance[i] == Integer.MAX_VALUE){ //도달할 수 없는 경우 무한(INFINITY) 출력
System.out.println("INFINITY");
}else{
System.out.println(distance[i]); //도달할 수 있는 경우 거리를 출력
}
});
}
// 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드 번호 반환
public static int getSmallestNode(){
int minValue = Integer.MAX_VALUE;
int index = 0; //가장 최단 거리가 짧은 노드(인덱스)
for(int i=0; i <= n; i++){
if(distance[i]<minValue && !visited[i]){
minValue = distance[i];
index = i;
}
}
return index;
}
// 다익스트라 알고리즘
public static void dijkstra(){
//시작 노드에 대해서 초기화
distance[start] = 0;
visited[start] = true;
IntStream.range(0, graph.get(start).size()).forEach(i->
distance[graph.get(start).get(i).getIndex()] = graph.get(start).get(i).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 = distance[now] + graph.get(now).get(j).getDistance();
// 현재 노드를 거쳐서 다른 노드를 이동하는 거리가 더 짧은 경우
if(cost < distance[graph.get(now).get(j).getIndex()])
distance[graph.get(now).get(j).getIndex()] = cost;
}
}
}
}· 시간복잡도: O(V^2)
- V: 노드의 개수
- 총 O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색하고, 현재 노드와 연결된 노드를 매번 일일이 확인함
- 최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 일반적으로 이 코드로 문제를 풀 수 있지만,
노드가 10,000개를 넘어가는 문제라면 이 코드로 문제를 풀기 어려움 -> 개선된 다익스트라 알고리즘 사용
개선된 다익스트라 알고리즘
· 시간복잡도: O(ElogV)
- V: 노드의 개수, E: 간선의 개수
· 최단 거리가 가장 짧은 노드를 찾는 과정의 속도를 개선했다.
<-> 간단한 다익스트라 알고리즘의 선형 탐색
· 힙 자료구조를 사용하여 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리한다.
-> 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있음 (시간 복잡도 개선: 선형 시간 -> 로그 시간)
힙(Heap)이란?
· 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조
· 다음과 같은 힙 속성(property)을 만족한다.
- A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
· 부모 노드가 자식 노드들보다 크다면 최대 힙(Max Heap)구조, 부모 노드가 자식 노드들보다 작다면 최소 힙 구조(Min Heap)라고 함
· 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
- 예: 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인
· 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나
우선순위 큐(Priority Queue)란?
· 각 원소들이 우선순위를 갖고, 높은 우선순위를 갖는 원소가 낮은 우선순위를 가진 원소보다 먼저 처리되는 구조
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제
· 우선순위 큐를 구현할 때 내부적으로 최소 힙(Min Heap) 혹은 최대 힙(Max Heapa)을 이용할 수 있다.
- 최소 힙에서 데이터를 삭제할 때 값이 낮은 데이터부터 먼저 삭제하고, 최대 힙은 값이 높은 데이터를 먼제 삭제한다.
- 최소 힙을 최대 힙처럼 사용하는 방법: 우선순위에 해당하는 값에 음수 부호를 붙여서 넣었다가,
나중에 우선순위 큐에서 꺼낸 후 다시 음수 부호를 붙여서 원래 값으로 되돌린다.
· 우선순위 큐를 리스트를 이용해 구현할 수도 있다.
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
| 리스트 | O(1) | O(N) |
| 힙(Heap) | O(logN) | O(logN) |
· 데이터의 개수가 N개일 때, 힙 자료구조에 N개의 데이터를 모두 넣은 뒤에 다시 모든 데이터를 꺼낸다고 가정하자.
삽입할 때는 O(NlogN)의 시간 복잡도가 필요하고, 삭제할 때도 O(NlogN)의 시간 복잡도가 필요하다.
따라서, 전체 시간 복잡도는 O(NlogN)이다. 동일한 작업을 리스트를 이용해 수행하면 시간 복잡도는 O(N^2)이다.
· 힙을 이용하면, 모든 원소를 저장한 뒤 우선순위에 맞게 빠르게 뽑아낼 수 있으므로 '우선순위 큐' 구현시 가장 많이 사용된다.
· 대부분의 프로그래밍 언어에서 우선순위 큐 라이브러리를 지원한다.
- c++에서는 최대 힙, 자바에서는 최소 힙을 이용하여 각각 우선순위 라이브러리를 구현한다.
▶ 예시 - 힙을 이용하여 1번 노드에서 다른 모든 노드로 가는 최단 경로 구하기
· 최단 거리를 저장하기 위한 1차원 리스트(최단 거리 테이블)는 간단한 다익스트라 알고리즘에서와 동일하게 이용하고,
현재 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 추가로 이용한다.
· step 초기화.
출발 노드인 1번 노드에서 다른 노드로의 최단 거리를 표시할 테이블을 생성한다.
초기 상태에서는 다른 모든 노드로 가는 최단 거리를 모두 '무한'으로 초기화한다.
우선순위 큐에 1번 노드를 넣고, 거리를 0으로 설정한다.
즉, (거리: 0, 노드: 1)의 정보를 가지는 객체를 우선순위 큐에 넣는다. 이때 거리를 기준으로 우선순위 큐를 구성한다.
· step 0.
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 출발 노드에서 출발 노드로의 거리는 0이므로 출발 노드가 선택된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
| 우선순위 큐 | (거리:0, 노드:1) |
· step 1.
거리가 가장 짧은 노드를 선택한다. 기본적으로 거리가 짧은 원소가 우선순위 큐의 최상위 원소로 위치해 있다. 따라서 우선순위 큐에서 그냥 노드를 꺼내면 된다. 해당 노드를 이미 처리한 적이 있으면 무시하고, 아직 처리하지 않은 노드에 대해서만 처리한다.
꺼낸 원소는 (0,1)로 1번 노드까지 가는 최단 거리가 0이라는 의미다. 1번 노드를 거쳐서 2, 3, 4번 노드로 가는 최소 비용은 2(0+2), 5(0+5), 1(0+1)이다. 더 짧은 경로를 찾았으므로 각각 갱신한다.
이렇게 더 짧은 경로를 찾은 노드 정보들은 다시 우선순위 큐에 넣는다.
꺼낸 원소:(거리:0, 노드:1)
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 5 | 1 | 무한 | 무한 |
| 우선순위 큐 | (거리:1, 노드:4) (거리:2, 노드:2) (거리:5, 노드:3) |
· step 2.
우선순위 큐에서 원소를 꺼내서 동일한 과정을 반복한다. (1, 4) 값을 갖는 원소가 추출된다.
아직 노드 4를 방문하지 않았으며, 현재 최단 거리가 가장 짧은 노드는 4이다. 따라서 노드 4와 연결된 간선들을 확인한다.
4번 노드까지의 최단 거리는 1이므로, 4번 노드를 거쳐서 3번과 5번 노드로 가는 최소 비용은 4(1+3), 2(1+1)이다.
기존의 리스트에 담겨 있는 값들보다 작으므로 리스트를 갱신하고, 우선순위 큐에 (4, 3), (2, 5)라는 두 원소가 추가된다.
꺼낸 원소: (거리: 1, 노드: 4)
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
| 우선순위 큐 | (거리:2, 노드:2) (거리:2, 노드:5) (거리:4, 노드:3) (거리:5, 노드:3) |
· step 3.
우선순위 큐에서 원소 (2, 2)를 꺼낸다. (2번과 5번 노드까지의 최단 거리는 같으므로 둘의 처리 순서는 상관 x)
2번 노드를 거쳐서 가는 경우 중 현재의 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.
따라서 우선순위 큐에 어떠한 원소도 들어가지 않는다.
꺼낸 원소: (거리: 1, 노드: 4)
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 4 | 1 | 2 | 무한 |
| 우선순위 큐 | (거리:2, 노드:5) (거리:4, 노드:3) (거리:5, 노드:3) |
· step 4.
우선순위 큐에서 원소 (2, 5)를 꺼낸다. 5번 노드를 거쳐 3, 6번 노드로 갈 수 있다.
5번 노드까지의 최단 거리는 2이므로, 5번 노드를 거쳐서 3번과 6번 노드로 가는 최소 비용은 3(2+1), 4(2+2)이다.
기존의 리스트에 담겨 있는 값들보다 작으므로 리스트를 갱신하고, 우선순위 큐에 (3, 3), (4, 6)라는 두 원소가 추가된다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리:3, 노드:3) (거리:4, 노드:3) (거리:4, 노드: 6) (거리:5, 노드:3) |
· step 5.
원소(3, 3)을 꺼내서 3번 노드를 기준으로 알고리즘을 수행한다.
최단 거리 테이블이 갱신되지 않으므로 결과는 다음과 같다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리:4, 노드:3) (거리:4, 노드: 6) (거리:5, 노드:3) |
· step 6.
원소 (4, 3)을 꺼내서 3번 노드를 기준으로 알고리즘을 수행한다.
3번 노드는 이미 처리된 적이 있고 현재 최단 거리 테이블에서 3번 노드까지의 최단 거리는 3이므로,
3번 노드까지 가는 최단 거리는 4라는 방금 꺼낸 원소의 정보는 무시한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리:4, 노드: 6) (거리:5, 노드:3) |
· step 7.
원소 (4, 6)이 꺼내지고, 6번 노드에 대해서 처리한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 우선순위 큐 | (거리:5, 노드:3) |
· step 8.
마지막으로 남은 원소를 꺼내지만, 아까와 마찬가지로 처리된 노드이므로 무시한다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 거리 | 0 | 2 | 3 | 1 | 2 | 4 |
| 순위 큐 |
· 모든 단계를 거친 후 최단 거리 테이블에 남아 있는 0, 2, 3, 1, 2, 4가 각 노드로의 최단 거리다.
· 데이터의 개수가 N개일 때, 하나의 데이터를 큐에 삽입 및 삭제할 때 시간 복잡도는 O(logN)이다.
▶ 예시 - 개선된 다익스트라 알고리즘 구현
/*
입력값
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
*/
public class EnhancedDijkstraExam {
public static final int INF = Integer.MAX_VALUE; // 무한을 의미하는 값 설정
// 노드의 개수(n), 간선의 개수(m), 시작 노드 번호(start)
public static int n,m,start;
// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
public static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
// 최단 거리 테이블
public static int[] d = new int[100001];
private void dijkstra(int start){
PriorityQueue<Node> pq = new PriorityQueue<>();
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++){
Node otherNode = graph.get(now).get(i);
int cost = d[now] + otherNode.getDistance();
//현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if(cost<d[otherNode.getIndex()]){
d[otherNode.getIndex()] = cost;
pq.offer(new Node(otherNode.getIndex(),cost));
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
// 그래프 초기화
IntStream.rangeClosed(0,n).forEach(i-> graph.add(new ArrayList<Node>()));
//모든 간선 정보 입력
IntStream.range(0,m).forEach(i->{
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph.get(a).add(new Node(b,c)); //a번 노드에 서 b번 노드로 가는 비용이 c임
});
//최단 거리 테이블을 모두 무한으로 초기화
Arrays.fill(d,INF);
//다익스트라 알고리즘 수행
EnhancedDijkstraExam dijkstraExam = new EnhancedDijkstraExam();
dijkstraExam.dijkstra(start);
//모든 노드로 가기 위한 최단 거리를 출력
IntStream.rangeClosed(1,n).forEach(i->{
if(d[i] == INF) System.out.println("INFINITY"); //도달할 수 없는 경우, 무한(INFINITY)라고 출력
else System.out.println(d[i]); //도달할 수 있는 경우 거리를 출력
});
}
static class Node implements Comparable<Node> {
private int index;
private int distance;
Node(int index, int distance){
this.index = index;
this.distance = distance;
}
public int getDistance() {
return distance;
}
public int getIndex() {
return index;
}
// 거리(비용)가 짧은 것이 높은 우선순위를 가지정록 설정
@Override
public int compareTo(Node o) {
return o.distance - this.distance;
}
}
}· 한 번 처리된 노드는 더 이상 처리하지 않는다.
즉, 큐에서 노드를 하나씩 꺼내 검사하는 while문은 노드의 개수 V 이상의 횟수로 반복되지 않는다.
또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다.
따라서 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 총 최대 간선의 개수(E) 만큼 연산이 수행될 수 있다.
· 다익스트라 최단 경로 알고리즘은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사한다.
힙에 N개의 데이터를 모두 넣고, 이후에 모두 빼는 과정은 O(NlogN)이다.
즉, 다익스트라 최단 경로 알고리즘의 사간복잡도는 O(ElogE)와 유사하다.
· 이때, 중복 간선을 포함하지 않는 경우, E는 항상 V^2 보다 작다.
모든 노드끼리 서로 다 연결되어 있을 때 간선의 개수를 약 V^2으로 볼 수 있고, E는 V^2이하이기 때문이다. 즉, logE < logV^2이다.
이때, O(logV^2)은 O(2logV)이고 이는 O(logV)이다. 따라서 다익스트라 알고리즘의 전체 시간 복잡도는 O(ElogV)이다.
플로이드 워셜 알고리즘
| 다익스트라 알고리즘 | 플로이드 워셜 알고리즘 |
| · 한 지점에서 다른 특정 지점까지의 최단 경로를 구할때 사용 | · 모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구할때 사용 |
| · 출발 노드가 1개 · 다른 모든 노드까지 최단 거리를 저장하기 위해 1차원 리스트 사용 |
· 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 저장하기 위해 2차원 리스트 이용 |
| · 그리디 알고리즘 | · 다이나믹 프로그래밍 (노드가 N개 일 때, N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트 갱신) |
| · 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. |
· 단계마다 거쳐 가는 노드를 기준으로 알고리즘 수행한다는 점이 다익스트라 알고리즘과 동일하다. · 하지만 매번 방문하지 않는 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다. |
· 노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행하고,
단계마다 O(N^2)의 연산으로 현재 노드를 거쳐 가는 모든 경로 고려한다.
· 플로이드 워셜 알고리즘의 총시간 복잡도: O(N^3)
· 노드의 개수가 적은 경우 플로이드 워셜을 이용할 수 있지만,
노드와 간선의 개수가 모두 많은 경우 우선순위 큐를 이용하는 다익스트라 알고리즘을 이용하면 유리하다.
· 플로이드 워셜 알고리즘의 원리
1. 노드와 간선을 확인하고 최단 거리 테이블 생성한다.
- 이동할 수 없는 경로는 무한대로 입력하고, 자기 자신에서 자기 자신으로 가는 비용은 0으로 입력한다.
2. 1번 노드를 거쳐 가는 경우를 고려하여 최단 거리를 갱신한다.
- 현재 확인하고 있는 노드를 제외하고, N-1개의 노드 중 서로 다른 노드 (A,B)쌍을 선택하여,
A -> B 비용보다 A -> 1번 노드 -> B로 가는 비용이 더 작다면 최단 거리 갱신
3. 나머지 모든 노드에 대하여 똑같은 로직을 수행한다.
· 단계마다 n-2P2개의 쌍을 반복하고, O(n-1P2)는 O(n^2)이므로, 전체 시간 복잡도는 O(n^3)이다.
- nPm: 순열(permutation), 서로 다른 n개에서 서로 다른 m개를 뽑아 나열하는 경우의 수
· K번의 단계에 대한 점화식 = Dab = min(Dab, Dak + Dkb)
- 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교하여 더 작은 값으로 갱신한다.
- 3중 반복문을 이용하여 위 점화식에 따라 최단 거리 테이블을 갱신한다.
▶ 예시
· step 0.
위와 같은 그래프에서, 초기 테이블을 생성한다.
연결된 간선을 값을 채워 넣고, 연결되지 않은 간선은 '무한'이라는 값을 넣는다.
2차원 리스트에서 각 값에 해당하는 Dab는 a에서 b로 가는 최단 거리다.
자신에서 자신으로 가는 비용은 0이므로, (1<=i<=n)의 범위를 가지는 모든 i에 대하여 Dii는 0이다.
· step 1.
1번 노드를 거쳐 가는 경우를 고려한다.
6 = 3P2가지 경우에 대해서 고민하면 된다.
D23 = min(D23, D21 + D13)
D24 = min(D24, D21 + D14)
D32 = min(D32, D31 + D12)
D34 = min(D34, D31 + D14)
D42 = min(D42, D41 + D12)
D43 = min(D43, D41 + D13)
위 6가지 경우를 하나씩 확인하며 값을 갱신한다.
예를 들어 D23 = min(D23, D21 + D13)은 기존의 2번 노드에서 3번 노드로 가는 비용보다,
2번 노드에서 1번 노드를 거쳐 3번 노드로 가는 비용이 더 작다면, 그것으로 갱신한다는 의미다.
갱신한 값은 아래와 같다.
· step 2.
현재 테이블의 상태는 다음과 같다.
이번에는 2번 노드를 거쳐 가는 경우를 계산하므로 2번 노드를 제외한 1번, 3번, 4번 노드에서 2개의 노드를 뽑는 경우를 고려한다.
-> (1, 3), (1, 4), (3, 1), (3,4), (4, 1), (4,3) 6가지
6가지 경우(하늘색 표시)에 대해서 고려하여 갱신한 결과를 다음과 같다.
· step 3.
동일한 방식으로 3번 노드를 거쳐 가는 경우를 계산 한다.
· step 4.
동일한 방식으로 4번 노드를 거쳐 가는 경우를 계산 한다.
· 최종 결과
노드의 개수가 4개이므로 총 step 4까지 알고리즘을 수행했다.
최종적인 테이블 형태는 아래와 같고, 모든 노드에서 모든 노드로 가는 최단 거리 정보를 표현한다.
▶ 예시 - 플로이드 워샬 알고리즘 소스코드
/*
입력 예시
4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
*/
public class FloydWarshallExam {
public static void main(String args[]){
int INF = (int) 1e9; //무한을 의미하는 값 10억(둘을 더하여도 21억 이하인 충분히 큰 숫자)
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); //노드의 개수
int m = sc.nextInt(); //간선의 개수
int[][] graph = new int[n+1][m+1];// 2차원 최단 거리 테이블 만들기
//최단 거리 테이블을 모두 무한으로 초기화, 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
IntStream.rangeClosed(0,n).forEach(i->{
Arrays.fill(graph[i],INF);
graph[i][i] = 0;
});
//간선에 대한 정보를 입력 받아, 그 값으로 초기화
IntStream.range(0, m).forEach(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();
}
}
}
'알고리즘&코딩테스트' 카테고리의 다른 글
| [Algorithm] 그리디 알고리즘(Greedy Algorithm)이란? (0) | 2021.11.04 |
|---|---|
| [Algorithm] 그래프 이론: 트리, 서로소, 신장 트리, 크루스칼 알고리즘, 위상 정렬 (0) | 2021.11.03 |
| [Algorithm] 이것이 코딩테스트다 - 이진탐색 문제풀이(with 자바) (0) | 2021.09.13 |
| [Algorithm] 순차 탐색과 이진 탐색 (0) | 2021.09.06 |
| [Algorithm] 정렬 알고리즘 (with 자바코드) (5) | 2021.02.26 |
댓글