다익스트라 알고리즘이란?
- 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단 거리를 구하는 알고리즘
-> 쉽게 그래프의 최단 경로를 구하는 알고리즘
-> 하나의 정점에서 출발하는 최단 거리(출발지만 정의) - 인접 행렬로 표현된 그래프의 경우 O(n^2)의 시간복잡도를 가지지만, 우선순위 큐 등을 이용해 O((V+E)log n)까지 낮출 수 있음
-> 만일 연결 그래프라면 O(E log N)까지 시간 복잡도를 줄일 수도 있음 - 탐욕법과 동적 계획법 사용
※ 음의 가중치를 가지면 안되는 이유는, 최소 비용의 음의 무한대 발산, 그리디 알고리즘 적용 불가능이 있다. 조금 더 자세한 설명은 아래에 있다.
※ 연결 그래프 : 모든 두 꼭짓점 사이에 경로가 존재하는 그래프
※ 희소 그래프 : 밀집 그래프의 반대, 밀집 그래프란, 간선의 수가 최대에 가까운 그래프. 보통, 간선의 총 개수가 정점의 개수^2와 근사하다면 밀집 그래프이다.
※ 최단 거리를 구하는 알고리즘이라는 측면에서, 출발지 하나를 고른다는 것은 '벨만-포드' 알고리즘과 같다. 하지만 둘의 차이점은 존재한다.
-> 다익스트라는 음의 가중치를 허용하지 않지만, 벨만-포드는 허용한다.
-> 다익스트라는 O(m log N)의 시간복잡도를 갖고, 벨만-포드는 O(mn)의 시간복잡도를 갖는다.
다익스트라 알고리즘 풀이
- 기본적으로 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용하는 알고리즘이다.
- 기본적으로 아래 2개의 단계를 반복하여 임의의 노드에서 각 모든 노드까지의 최단거리르 구한다. 임의의 노드에서 다른 노드로 가는 값을 비용이라고 한다.
-> 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택(그리디 알고리즘)
-> 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신(다이나믹 프로그래밍)
만약 아래와 같은 그림과 같은 A노드에서 출발하여 E노드로 가는 최단 경로를 구하는 문제에 다익스트라 알고리즘을 적용시킨다고 하면 아래와 같다.
각 단계마다 기준이 있어야 하기 때문에, 방문하지 않은 노드의 집합을 Before, 방문한 노드를 After, 현재까지 A노드가 방문한 곳 까지의 최소 비용을 Dist[대상 노드]라고 정의한다면, 현재 시점에서 각 집합이 가지고 있는 값은 아래와 같을 것이다.
Before = {A,B,C,D,E}
After = {}
Dist[A] = ?
Dist[B] = ?
Dist[C] = ?
Dist[D] = ?
Dist[E] = ?
▶ 초기화
현재상태에서 방문하지 않은 노드 중에서 가장 비용이 적은 대상 노드는 어디일까? A노드에서 다른 간선으로 가는 비용이 0인 간선이 존재하지 않는다면 다연히 A노드일 것이다. 또한, 그러한 값이 존재한다고 해도 첫 번째 단계에서 'A노드에서 A노드로 가는 지점이 가장 짧다' 라고 그냥 정의하고 시작하게 된다. 즉, 첫 번째 단계에서는 가장 비용이 적은 노드를 선택할 기준이 없기 때문에 출발지인 A노드 자신을 초기 선택 노드로 초기화한다. 즉 현 상태에서 집합을 보면 아래와 같다.(아직 A노드를 방문하지는 않았지만 A노드에서 A노드로 가는 비용이 가장 적다고 정의한 상태)
Before = {A,B,C,D,E}
After = {}
Dist[A] = 0
Dist[B] = ?
Dist[C] = ?
Dist[D] = ?
Dist[E] = ?
▶ 알고리즘 적용
초기화가 끝났다면, 위에 말한 논리를 반복해서 적용하면 된다. 위 상태에서 방문하지 않은 노드 중 가장 비용이 적은 대상 노드? 당연히 A노드일 것이다. 또한, A노드를 기준으로 갈 수 있는 인접 노드로의 최소 비용은 얼마일까? 결과는 아래와 같을 것이다.
Before = {A,B,C,D,E}
After = {}
Dist[A] = 0
Dist[B] = 2
Dist[C] = 5
Dist[D] = 3
Dist[E] = ?
이후에는 앞선 단계를 계속 반복하면 된다. 현재 상태에서 방문하지 않은 노드 중 가장 비용이 적은 노드는? A노드는 방문 하였기 대문에 B노드가 될 것이다. 따라서 B노드를 방문하고, B노드와 인접한 노드들의 최소 비용을 갱신해주면 된다.
Before = {A,B,C,D,E}
After = {}
Dist[A] = 0
Dist[B] = 2
Dist[C] = 5
Dist[D] = 3
Dist[E] = ?
※ B노드에서 C노드로 가는 비용은 9이다. 하지만 이미 C노드로 가는 최소 비용이 5이므로 갱신할 필요가 없다.
다음 단계도 마찬가지이다. A노드와 B노드를 방문하였기 때문에, 그 중에서 가장 비용이 적은 노드인 D노드를 선택하고, 방문한 뒤 같은 과정을 짆애해주면 된다. 그렇다면 아래와 같을 것이다.
Before = {A,B,C,D,E}
After = {}
Dist[A] = 0
Dist[B] = 2
Dist[C] = 4
Dist[D] = 3
Dist[E] = ?
※ D노드를 거쳐 C노드로 가는 비용은 4이고, 현재까지 C노드로 가는 최소 비용은 5였기 때문에 Dist[C]를 4로 갱신할 수 있다.
Before = {A,B,C,D,E}
After = {}
Dist[A] = 0
Dist[B] = 2
Dist[C] = 4
Dist[D] = 3
Dist[E] = 9
Before = {A,B,C,D,E}
After = {}
Dist[A] = 0
Dist[B] = 2
Dist[C] = 4
Dist[D] = 3
Dist[E] = 9
마지막으로 방문하는 E노드에서는 더 이상 갈 수 있는 노드가 존재하지 않으므로, 방문만 완료하고 알고리즘을 종료해준다.
다익스트라 알고리즘 구현
- O(V^2)
- 한 번 방문한 배열은 방문할 수 없으므로 방문 여부를 체크할 배열이 필요하고, 각 노드까지의 최소 비용을 저장할 배열이 필요하다
- 구현에서 고려해 주어야 하는 것은, 미방문 지점의 값을 항상 최소의 값으로 갱신하는 것이 목표이기에, 미방문 지점은 매우 큰 값으로 초기화하여 로직을 처리한다(노드가 가질 수 있는 최대 비용을 넣어두면 좋다)
- 최소 비용을 갖는 노드를 선택하는 과정은 최악의 경우 모든 노드를 확인해야 하고, 이것이 V번 반복하기 때문에 O(V^2)의 시간 복잡도를 갖는다.
// 도착 지점과, 도착지점으로 가는 비용을 담은 class
class Node {
int idx;
int cost;
// 생성자
Node(int idx, int cost){
this.idx = idx;
this.cost = cost;
}
}
public class Dijkstra{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//노드와 간선의 개수
int V = sc.nextInt();
int E = sc.nextInt();
// 출발지점
int start = sc.nextInt();
//1. 인접리스트를 이용한 그래프 초기화
ArrayList<ArrayList<Node>> graph = new ArrayList<>();
//노드의 번호가 1부터 시작해, 0번 인덱스 부분을 임의로 만들어 놓기만 하기
for(int i=0; i<V+1; i++){
graph.add(new ArrayList<>());
}
//그래프에 값을 넣는다
for(int i=0; i<E; i++){
//a부터 b로 가는 값은 cost
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
graph.get(a).add(new Node(b,cost));
}
//2. 방문 여부를 확인할 boolean 배열, start노드부터 end 노드까지의 최소 거리르 저장할 배열 만들기
boolean[] visit = new boolean[V+1];
int[] dist = new int[V+1];
//3. 최소 거리 정보를 담을 배열을 초기화
for(int i=0; i<V+1; i++){
//출발 지점 외 나머지 지점까지의 최소 비용은 최대로 지정해두기
dist[i] = Integer.MAX_VALUE;
}
//출발 지점의 비용은 0으로 시작
dist[start] = 0;
//4. 다익스트라 알고리즘 진행
//모든 노드를 방문하면 종료하기 때문에, 노드의 개수만큼 반복
for(int i=0; i<V; i++){
//4-1. 현재 거리 비용 중 최소인 지점 선택
//해당 노드가 가지고 있는 현재 비용
int nodeValue = Intger.MAX_VALUE;
//해당 노드의 인덱스(번호)
int nodeIdx = 0;
// 인덱스 0은 생각하지 않기 때문에 0부터 반복 진행
for(int j=1; j<V+1; j++){
//해당 노드를 방문하지 않았고, 현재 모든 거리비용 중 최솟값을 찾는다.
if(!visit[j] && dist[j] < nodeValue){
nodeValue = dist[j];
nodeIdx = j;
}
}
//최종 선택된 노드를 방문처리
visit[nodeIdx] = true;
//4-2. 해당 지점을 기준으로 인접 노드의 최소 거리 값을 갱신
for(int j=0; j<graph.get(nodeIdx)size(); j++){
//인접 노드를 선택
Node adjNode = graph.get(nodeIdx).get(j);
//인접 노드가 현재 가지는 최소비용과
// 현재 선택된 노드의 값 + 현재 노드에서 인접 노드로 가는 값을 비교하여 더 작은 값으로 갱신
if(dist[adjNode.idx] > dist[nodeIdx]+adjNode.cost){
dist[adjNode.idx] = dist[nodeIdx]+adjNode.cost;
}
}
}
//5. 최종 비용을 출력
for(int i=1; i<V+1; i++){
if(dist[i] == Integer.MAX_VALUE){
System.out.println("INF");
} else{
System.out.println(dist[i]);
}
}
sc.close();
}
}- O((V+E)log V) -> 우선순위 큐 이용
- 기본적인 다익스트라 알고리즘은 최소 비용을 갖는 노드를 선택하고, 주변 노드의 값을 갱신하였다. 따라서 비용을 나타내는 배열에서 노드를 제외하고는 여전히 INF값을 갖기 때문에 굳이 고려해줄 필요가 없다. 즉, 갱신하는 주변 노드의 값에 대해서만 다음 최소 비용을 갖는 노드를 선택해주면 된다는 것이 우선순위큐를 이용하는 핵심이다.
- 우선순위 큐에 들어가는 노드의 수 = 갱신해야하는 주변 노드의 수이다. 이 말을 다르게 하면, 갱신해야하는 주변 노드의 수 = 갱신해야 하는 주변 노드로의 간선의 수인 것이다. 즉, 우선순위 큐에 삽입하는 최대 횟수는 간선의 개수이다. 따라서, 모든 간선에 대해 삽입 연산이 발생하기 때문에 최대 O(E log E)의 시간이 걸릴 수 있다. 하지만, 희소 그래프의 경우 E <= V^2이므로, 최대 O(E log V)의 시간이 걸린다고도 볼 수 있다. 각 노드들을 우선순위 큐에 추출해주는 연산에 대해서 최대 V개의 노드에 대해 우선순위 큐에서 추출할 것이므로 최대 O(V log V)의 시간이 걸릴 것이고, 따라서 최대 모든 노드, 간선에 대해 우선순위 큐를 계산해줘야 하므로 O((V+E)log V)의 시간이 걸릴 것이다.
※ 주의점
- 우선순위 큐에 넣는 다음 노드는 최소 비용으로 선택된 노드의 주변 노드이라고 위에 기술하였는데, 이 주변 노드를 무차별적으로 우선순위 큐에 넣고 무차별적으로 검사를 하면 문제가 발생한다. 즉, 최소 비용으로 뽑은 노드의 방문 체크를 하지 않은 경우와, 갱신이 이루어 지지 않은 노드까지 우선순위 큐에 넣는 경우, 모두 중복된 노드를 재방문 하게되는 문제가 발생한다.
- 시간 복잡도의 핵심은 poll()과 offer() 연산에 있다. 만일, 중복 노드를 무차별적으로 큐에 넣는다면 위에서 결과적으로 말한 최대 V개의 노드에서 우선순위 큐를 추출하는 O(V log V)가 보장되지 못한다. 따라서, 중복 노드 방문을 두 가지 조건을 기반으로 방지한다.
public class Dijkstra{
static int V,E,start;
static ArrayList<ArrayList<Node>> graph;
static class Node {
int idx, cost;
Node(int idx, int cost){
this.idx = idx;
this.cost = cost;
}
}
public static void main(String[] args) throws IOException{
//초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringToeknzier(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
start = Integer.parseInt(br.readLine());
graph = new ArrayList<ArrayList<Node>>();
for(int i=0; i<V+1; i++){
graph.add(new ArrayList<>());
}
for(int i=0; i<E; i++){
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
//유향 그래프로 예를 든다.
graph.get(s).add(new Node(e,c));
}
//다익스트라 알고리즘 초기화
int[] dist = new int[V+1]; //최소비용을 저장할 배열
for(int i=0; i<V+1; i++){
dist[i] = Integer.MAX_VALUE;
}
//주의점 1. 다익스트라 알고리즘의 최소비용을 기준으로 추출해야 한다. 최대 비용을 기준으로 하는 경우 최악의 경우 지수시간 만큼의 연산을 해야함.
PriorityQueue<Node> q = new PriorityQueue<Node>((o1,o2) -> Integer.compare(o1.cost, o2.cost));
//시작 노드에서, 시작 노드로 가는 값이 초기에 가장 짧은 비용을 갖는 노드
//즉, 도착 정점은 start, 비용은 0인 노드를 가장 먼저 선택할 것
q.offer(new Node(start, 0));
//해당 노드를 선택한 것이나 마찬가지이므로, dist[start] = 0으로 갱신
dist[start] = 0;
while(!q.isEmpty()){
Node curNode = q.poll();
//목표 정점이 꺼내 졌다면, 해당 노드까지는 최솟값 갱신이 완료 되었다는 것이 확정이다.
//따라서, 반복문을 종료해도 되지만, 이 코드는 시작 정점에 대하여 모든 정점으로의 최단 경로를 구하는 것을 가정한다.
//아래 주석 코드는 목표 정점이 구해졌다면 빠르게 탈출할 수 있는 조건이다! 문제에 따라 활용 가능할 것
//if(curNode.idx == end){
// System.out.pringln(dist[curNode.idx]);
// return;
//}
//꺼낸 노드 = 현재 최소 비용을 갖는 노드
//즉, 해당 노드의 비용이 현재 dist배열에 기록된 내용보다크다면 고려할 필요가 없으므로 스킵
//주의점 2. 중복노드 방지 1 -> 만일, 이 코드를 생략한다면, 위에 언급한대로 이미 방문한 정점을 '중복하여 방문'하게 된다.
//만일 그렇게되면, 큐에 있는 모든 다음 노드에 대하여 인접 노드에 대한 탐색을 다시 진행하게 된다.
// 그래프 입력이 만일 완전 그래프의 형태로 주어진다면, 이 조건을 생략한 것만으로 시간 복잡도가 E^2에 수렴할 가능성이 생긴다
if(dist[curNode.idx] < curNode.cost) continue;
//선택된 노드의 모든 주변 노드를 고려하기
for(int i=0; i<graph.get(curNode.idx).size(); i++){
Node nextNode = graph.get(curNode.idx).get(i);
//만일 주변 노드까지의 현재 dist값(비용)과 현재 선택된 노드로부터 주변 노드로 가는 비용을 비교하고, 더 작은 값을 선택
//주의점 3 : 중복노드 방지 2 -> 만일, 조건문 없이 조건문의 내용을 수행한다면 역시 중복 노드가 발생한다.
//간선에 연결된 노드를 모두 넣어준다면 앞서 언급한 정점의 시간 복잡도 V log V를 보장할 수 없다.
// 마찬가지로 E^2에 수렴할 가능성이 생긴다. 따라서 이 조건 안에서 로직을 진행해야만 한다.
if(dist[nextNode.idx] > curNode.cost+nextNode.cost){
dist[nextNode.idx] = curNode.cost + nextNode.cost;
//갱신된 경우메나 큐에 넣기
q.offer(new Node(nextNode.idx, dist[nextNode.idx]));
}
}
}
System.out.println(Arrays.toString(dist));
}
}다익스트라 알고리즘 정당성 증명
- 제대로 증명하려면 복잡하지만 간단하게 기술해보면 아래와 같다
- 먼저, 매번 현재 최소 비용을 갖는 노드를 선택했다. 하지만 자세히 살펴보면, 이렇게 선택이 된 노드는 다익스트라 알고리즘이 모든 노드를 방문할 때까지(알고리즘 종료될 때까지)최소 비용의 갱신이 더 이상 이루어지지 않았다는 점을 알 수 있다.(갱신 되는 노드는 아직 선택되지 않은 노드들에 대해서만 이뤄지고 있음)
- 최소 비용을 갖는 노드로 선택이 되었다면, 그 노드는 앞으로 다른 노드를 방문하는 것과 관계없이 항상 값이 갱신되지 않는다는 것이다. 다익스트라 알고리즘은 이 명제를 이용하여 정당성을 증명한다.(이 명제가 참이라면, 모든 노드에 대한 방문을 완료했을 때, 각 노든느 최솟값을 가지고 있을 것이다.)
제대로 된 증명을 알고싶다면, 아래 링크를 참고하길 바란다.
ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
