다익스트라 알고리즘
그래프 최단 거리 구하는 알고리즘
1. 다익스트라(Dijkstra)
2. 벨만-포드(Bellman-Ford)
3. 플로이드-와샬(Floyd-Warshall)
시작정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
✔️ 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식
✔️ 탐욕 기법 + DP을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사
벨만-포드와 차이점
| 다익스트라 | 벨만-포드 | |
|---|---|---|
| 음수 가중치 | X | O |
| 음수 사이클 | X | X |
| 시간복잡도 | O(mlogn) | O(mn) |
주의사항
음의 가중치는 허용하지 않는다
☁️ 왜 음의 가중치는 허용되지 않는가?그리디를 통해 최단 경로라고 여겨진 경로 비용을 DP 테이블에 저장한 뒤에 재방문하지 않는다. 이때 만약 음의 가중치가 있다면 이러한 규칙이 어긋날 수 있기 때문이다.
간단한 예로, 노드 A에서 노드 C로 가는 경로가 있고, 이 경로의 가중치가 음수인 경우를 가정해보자. 그리디 접근으로는 A에서 C로 바로 이동하는 것이 최단 경로로 선택될 것이다. 하지만 음의 가중치가 있으면, A에서 B로 가는 경로를 통해 노드 B의 가중치를 계속 누적해가면서 C로 가는 것이 더 나은 최단 경로가 될 수 있다.
따라서, 음의 가중치가 있는 경우에는 단순한 그리디 접근만으로 최단 경로를 찾는 것이 어려울 수 있으며, 이러한 상황에서는 DP 테이블에 저장된 값이 최적해를 보장하지 못할 수 있다.
과정
☁️ 1. 아직 방문하지 않은 정점 중 출발지로부터 가장 거리가 짧은 정점을 방문한다. 2. 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신한다.- 예시
pq는 우선순위 큐로 정점과 출발지에서 정점까지 가는 최소 거리를 저장한다. 우선순위는 거리가 짧을수록 높다.check는 boolean 배열로 해당 정점을 방문하는지 체크한다.dist는 int 배열로 출발지에서 최소 거리를 기록한다.
1) 출발지 4를 우선순위 큐에 넣는다. 출발지이므로 거리는 0이다. 
2) 우선순위 큐에서 하나 꺼내 nowVertex에 저장하고 방문체크를 한다.nowVertex을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신한다.
nowVertex는 4이다. 정점 4와 인접한 정점은 1과 5가 있다.-
dist[1]= 8로 변경처음 정점은 출발지이다. 출발지에서 정점 1로 가는 거리는 8이므로 dist[1] 값을 갱신해준다. 우선순위 큐에 정점 1과 출발지에서 정점 1까지 가는 거리(=8)을 추가해준다.(1, 8)
-
dist[5]= 3로 변경위와 동일한 이유로 값을 갱신하고 우선순위 큐에 값을 추가한다.(5, 3)3) 우선순위 큐에 값이 있으므로 하나 꺼내
nowVertex에 저장하고 방문 처리한다.
nowVertex= 5이고 방문하지 않았으므로 방문 체크 후 인접 정점 살펴본다. 정점 5과 인접한 정점은 4와 2가 있다. -
dist[2]= 34로 값 변경출발지에서 정점 2로 가는 값을 살펴준다. 이 때 경우는 2가지이다.
① 지금까지 계산한 출발지 ~ 정점 2 최단 거리 =
dist[2]② 출발지에서 정점 5를 지나서 정점 2를 가는 거리 =
dist[5]+ 정점 5에서 정점 2로 가는 거리(=간선의 가중치)과 ②를 비교하여 더 작은 값을
dist[2]에 기록한다.①과 ② 를 계산해보자.
①
dist[2]= 무한②
dist[5]+ 정점 5에서 정점 2로 가는 거리 = 3 + 31 = 34① > ② 이므로 값을 갱신하고 우선순위 큐에 해당 정점을 추가한다.(2, 34)
-
dist[4]값 변경 x① `dist[4]` = 0이다. ② `dist[5]` + 정점 5에서 정점 4로 가는 거리 = 3+ 9 = 12이다. ① < ② 이므로 값 갱신하지 않는다.4) 우선순위 큐에서 값을 꺼낸다.
nowVertex= 1이고 방문하지 않았으므로 방문 체크 후 인접 정점 살펴본다. 정점 1과 인접한 정점은 2와 3이 있다. -
dist[2]= 18로 값 변경①
dist[2]= 34②
dist[1]+ 정점 1에서 정점 2로 가는 거리 = 8 + 10 = 18① > ② 이므로 값을 갱신하고 우선순위 큐에 해당 정점을 추가한다.(2, 18)
-
dist[3]= 13로 값 변경① `dist[3]` = 무한 ② `dist[1]` + 정점 1에서 정점 3로 가는 거리 = 8 + 5 = 13 ① > ② 이므로 값을 갱신하고 우선순위 큐에 해당 정점을 추가한다.(3, 13)5) 우선순위 큐에서 값을 꺼낸다.
nowVertex= 3이고 방문하지 않았으므로 방문 체크 후 인접 정점 살펴본다. 정점 3과 인접한 정점은 1과 5가 있다. -
dist[1]값 변경x①
dist[1]= 8②
dist[3]+ 정점 3에서 정점 1로 가는 거리 = 13 + 1 = 14① < ② 이므로 값을 갱신하지 않는다.
-
dist[2]값 변경x① `dist[2]` = 18 ② `dist[3]` + 정점 3에서 정점 2로 가는 거리 = 13 + 13 = 26 ① < ② 이므로 값을 갱신하지 않는다.6) 우선순위 큐에서 값을 꺼낸다.
nowVertex= 2이고 방문하지 않았으므로 방문 체크 후 인접 정점 살펴본다. 정점 2과 인접한 정점은 3이다. -
dist[3]값 변경x①dist[3]= 13②dist[2]+ 정점 2에서 정점 3로 가는 거리 = 18 + 2 = 20 -
① < ② 이므로 값을 갱신하지 않는다.
7) 우선순위 큐에서 값을 꺼낸다.
nowVertex= 2이고 방문했으므로 다음으로 넘어간다.8) 우선순위 큐가 비었으므로 다익스트라 알고리즘을 종료한다. 정점 4에서 출발하여 다른 정점까지 최소 거리는 다음 dist 배열과 같다.
-
구현
☁️ 개선된 다익스트라 알고리즘 구현을 위해 인접 리스트 그래프 + 우선순위 큐를 사용하였다.- 설명 •
Node클래스를 만든다. 이 클래스는 우선순위 큐에 정점번호 + 가중치 저장을 위해 만드는 것이다.class Node implements Comparable<Node>{ int index; int cost; //정점번호, 가중치 저장 public Node(int index, int cost) { this.index = index; this.cost = cost; } //cost(=가중치) 중심으로 우선순위가 정해지기 때문에 compareTo 오버라이딩 //다른 방법으로 이를 생략하고 우선순위 큐 아래처럼 선언 /** PriorityQueue<Node> pq = new PriorityQueue<Node> ((o1, o2) -> Integer.compare(o1.cost, o2.cost)); **/ @Override public int compareTo(Node o) { return Integer.compare(this.cost, o.cost); } }-
boolean check배열과int dist배열을 만든다.check배열은 정점을 방문했는지 확인하고,dist배열은 출발지로부터 거리가 얼마나 되는지 기록한다.dist배열은 INF(무한대) 값으로 초기화한다.boolean[] check = new boolean[n + 1]; int[] dist = new int[n + 1]; int INF = Integer.MAX_VALUE; Arrays.fill(dist, INF);• 출발지는 방문으로 표시하고
dist배열 해당 인덱스에 0으로 기록한다. 출발지 정점과 가중치를 우선순위 큐에 넣는다. 이때 우선순위는 가중치가 가장 작은 것이다.dist[start] = 0; PriorityQueue<Node> pq = new PriorityQueue<>(); pq.offer(new Node(start, 0));• 큐가 빌 때 까지 다음을 반복한다.
1) 큐 앞에 있는 값을 가져오고 삭제한다. 이를
nowVertex로 하겠다. 이때 가져온 값은 현재 큐에 있는 값 중 출발지로부터 가장 가까운 거리(=작은 가중치)를 가졌다.int nowVertex = pq.poll().index;2-1) 만약
nowVertex를 방문했다면 다시 1)로 돌아간다.2-2) 만약
nowVertex를 방문하지 않았다면 방문 처리 후 3)을 수행한다.3)
nowVertex과 인접한 정점들을 살핀다. 이때 하나의 인접정점을next로 하겠다.① 지금까지 출발지에서
next로 갈 때 가장 빠른 거리② 출발지에서
nowVertex방문 후next로 가는 거리① < ② 라면 지금까지 계산한 출발지-next 거리보다 출발지-
nowVertex-next거리가 더 짧다는 뜻이므로 값을 갱신하고 next 정점과 ②값을 우선순위 큐에 넣어준다.(출발지에서 갈 수 있는 정점이면 우선순위 큐에 넣어서 최단 거리를 계산해줘야 한다.)
//index의 연결된 정점 비교 for(Node next : graph[nowVertex]) { if(dist[next.index] > dist[nowVertex]+ next.cost) { dist[next.index] = dist[nowVertex] + next.cost; //값 갱신 pq.offer(new Node(next.index, dist[next.index])); } }
-
- 전체 코드
class Node implements Comparable<Node>{ int index; int cost; public Node(int index, int cost) { this.index = index; this.cost = cost; } @Override public int compareTo(Node o) { return Integer.compare(this.cost, o.cost); } } public class Main { static ArrayList<Node>[] graph; //노드의 크기, 출발지 public static void Dijkstra(int n, int start) { boolean[] check = new boolean[n + 1]; int[] dist = new int[n + 1]; int INF = Integer.MAX_VALUE; Arrays.fill(dist, INF); dist[start] = 0; PriorityQueue<Node> pq = new PriorityQueue<>(); pq.offer(new Node(start, 0)); while(!pq.isEmpty()) { int nowVertex = pq.poll().index; if(check[nowVertex]) continue; check[nowVertex] = true; //index의 연결된 정점 비교 for(Node next : graph[nowVertex]) { if(dist[next.index] > dist[nowVertex]+ next.cost) { dist[next.index] = dist[nowVertex] + next.cost; pq.offer(new Node(next.index, dist[next.index])); } } } //최소거리 출력 for(int i : dist) { if(i == INF) System.out.print(0 + " "); else System.out.print(i+" "); } } public static void main(String[] args) throws IOException { //그래프 입력 받기 BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); //정점의 개수, 간선의 개수 int n = Integer.parseInt(bf.readLine()); int m = Integer.parseInt(bf.readLine()); graph = new ArrayList[n+1]; for (int i = 0; i <= n; i++) graph[i] = new ArrayList<>(); StringTokenizer st; for(int i = 0 ; i < m; i++) { st = new StringTokenizer(bf.readLine()); int v = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); int cost = Integer.parseInt(st.nextToken()); graph[v].add(new Node(w, cost)); } int start = Integer.parseInt(bf.readLine()); //다익스트라 알고리즘 수행 Dijkstra(n, start); } }입력 5 9 1 2 10 1 3 5 2 3 2 3 1 1 3 2 13 4 1 8 4 5 3 5 4 9 5 2 31 4 3 출력 결과 0 8 18 13 0 3 //인덱스 0은 사용 x
시간 복잡도(V : 노드, E : 간선)
- 인접 행렬로 표현된 그래프 : O(V^2)
- 우선순위 큐 이용 : O(ElogV)
- 시간 복잡도 설명 ☁️ 다익스트라 알고리즘의 시간 복잡도 1. **방문하지 않은 노드 중 최단 거리 노드 찾기**: 그래프의 모든 노드를 반복하면서, 아직 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾습니다. 이를 위해 최소 우선순위 큐나 배열 등을 사용할 수 있습니다. - 이 단계에서 모든 노드를 한 번씩 검사하므로 O(V)의 시간이 소요됩니다. (V는 노드의 수) 2. **인접한 노드의 최단 거리 갱신**: 선택된 노드로부터 직접 이웃한 노드들의 최단 거리를 갱신합니다. 이때 이웃 노드의 거리를 업데이트하고 우선순위 큐를 재구성합니다. - 이 과정에서 각 노드마다 인접한 모든 간선을 검사하므로 O(E)의 시간이 소요됩니다. (E는 간선의 수) 최소 우선순위 큐를 사용하는 경우, 전체적인 다익스트라 알고리즘의 시간 복잡도는 O((V + E)logV)입니다. 여기서 logV는 우선순위 큐에서 최소값을 찾는 데 필요한 시간입니다. 간선의 수 E가 노드의 수 V보다 많을 때 (일반적으로 밀집되어 있는 그래프일 때), O(V^2)의 시간 복잡도를 갖는 단순한 배열 기반의 다익스트라 알고리즘도 사용될 수 있습니다. 다익스트라 알고리즘은 최단 경로를 찾는 과정에서 모든 노드와 간선을 살펴보기 때문에 이러한 시간 복잡도를 갖게 됩니다. 다익스트라 알고리즘의 시간 복잡도를 간단히 정리하면 다음과 같습니다: - **최소 우선순위 큐를 사용한 경우**: - 그래프의 노드 수를 V, 간선 수를 E라 할 때, - 시간 복잡도는 O((V + E)logV)입니다. - **배열을 사용한 경우** (간선의 수 E가 노드의 수 V보다 많을 때): - 시간 복잡도는 O(V^2)입니다. 이러한 시간 복잡도는 다익스트라 알고리즘이 그래프의 모든 노드와 간선을 조사하고, 최단 경로를 갱신하면서 진행하기 때문에 발생합니다. 최소 우선순위 큐를 사용하면 보다 효율적인 알고리즘이지만, 배열을 사용한 간단한 버전도 적용 가능합니다.
