Post

[자료구조] 다익스트라 알고리즘, 플로이드 워셜 알고리즘

2025-02-09 16:22 · java, naver-archive

원문: https://blog.naver.com/qoxmfaktmxj/223754134466

다익스트라(Dijkstra) 최단거리 알고리즘

한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘

도착 노드 뿐 아니라 모든 다른 노드까지 최단 경로로 방문해서 각 노드까지의 최단 경로를 모두 찾게 된다.

매번 최단 경로의 노드르 선택해서 탐색을 반복하는 방식

출발 노드와 도착 노드 설정
최단 거리 테이블 초기화
현재 위치한 노드의 인접 노드 중 방문하지 않은 노드 구별 후, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택 => 해당 노드 방문처리
해당 노드를 거쳐 다른 노드로 넘어가는 비용을 최단 거리 테이블에 업데이트
3~4번 반복

위 표를 확인했을 때, 쓰여진 숫자는 각 노드로 가는 비용이다. 1=>5로 가는 비용은 9로 설정되어 있고, 1=>2로 가는 비용은 3으로 설정되어 있다. 테이블로 나타내면 아래와 같다.

0	3	INF	8	9
3	0	2	INF	INF
INF	2	0	1	3
8	INF	1	0	INF
9	INF	3	INF(무한대)	0 (대각선은 자신)

🔹노드 1 선택 시, 1과 연결된 선은 2 4 5 이다.

2번 노드가 최소 비용이라 노드 1번은 방문 처리하고, 테이블 값 변화는 없다.

🔹노드 2 에서는 이미 노드 1번 방문 했고, 비용 커서 안가고, 2와 최소 비용으로 연결된 노드 3 방문 한다. 이 때, 1과 3은 연결되지 않아 INF인데, 1->2->3으로 방문되는 비용인 5를 알았으므로 , (1,3) => INF에서 5로 UPDATE 된다.

🔹노드 3 에서는 이미 노드2는 방문했으니까 4랑 5만 확인 한다. 4,5 중 4가 비용 1로 최소라서 여기로 간다. 이 때,

노드1 => 노드4로 가는 비용이 8 이었는데 1->2->3->4 로 가게 되면 3+2+1 = 6이다. 따라서 (1,4) => 8에서 6으로 UPDATE 된다.

🔹노드 4에서는 노드5로 가는 선이 없으며, 노드1과 노드3 모두 방문처리된 곳이므로, 업데이트가 없고, 알고리즘이 종료 된다.

import java.util.*;

public class test6 { private static final int INF = Integer.MAX_VALUE; // 무한대를 나타냄

public static int[] dijkstra(int[][] graph, int start) { int n = graph.length; int[] dist = new int[n]; // 시작 노드로부터의 최단 거리 배열 boolean[] visited = new boolean[n]; // 방문 여부 체크

Arrays.fill(dist, INF); dist[start] = 0; // 시작 노드는 거리 0

PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); pq.offer(new int[]{start, 0});

while (!pq.isEmpty()) { int[] node = pq.poll(); int u = node[0];

if (visited[u]) continue; visited[u] = true;

for (int v = 0; v < n; v++) { if (graph[u][v] != INF \&\& !visited[v]) { int newDist = dist[u] + graph[u][v]; if (newDist < dist[v]) { dist[v] = newDist; pq.offer(new int[]{v, newDist}); } } } } return dist; // 최단 거리 배열 반환 }

public static void main(String[] args) { int INF = Integer.MAX_VALUE;

int[][] graph = { {0, 3, INF, 8, 9}, {3, 0, 2, INF, INF}, {INF, 2, 0, 1, 3}, {8, INF, 1, 0, INF}, {9, INF, 3, INF, 0} };

int[] shortestDistances = dijkstra(graph, 0); // 1번 노드에서 시작

// 최단 거리 출력 System.out.println(“노드 1부터 각 노드까지의 최단 거리:”); for (int i = 0; i < graph.length; i++) { System.out.println(“1 → “ + (i + 1) + “ : “ + (shortestDistances[i] == INF ? “INF” : shortestDistances[i])); }

// 갱신된 거리 행렬 출력 System.out.println(“\n갱신된 거리 행렬:”); for (int i = 0; i < graph.length; i++) { for (int j = 0; j < graph.length; j++) { if (i == 0) { // 1번 노드(배열 인덱스 0) 기준으로 갱신 System.out.print((shortestDistances[j] == INF ? “INF” : shortestDistances[j]) + “\t”); } else { System.out.print((graph[i][j] == INF ? “INF” : graph[i][j]) + “\t”); } } System.out.println(); } } }

노드 1에서의 값만 일단 업데이트 해서 위의 표를 재구성해 보았다.

🔹 1. 현재 INF가 남아 있는 이유

지금은 “노드 1에서 출발” 해서 각 노드까지의 최단 거리를 구한 상태야.

그렇기 때문에 노드 1에서 도달할 수 없는 곳은 여전히 INF로 남아 있어.

예를 들어, INF가 남아 있는 부분을 보면:

노드 2 → 4, 노드 2 → 5 는 여전히 INF
노드 4 → 2, 노드 4 → 5 도 INF

즉, 노드 1에서 출발했을 때 도달할 수 없었던 곳들은 아직 해결되지 않음.

🔹 2. 다른 노드에서 출발하면 INF가 줄어들까?

맞음!

다른 노드를 출발점으로 다익스트라를 실행하면, 새로운 최단 거리 경로를 찾을 수 있음!

예를 들어,

노드 2에서 출발하면 → 노드 3을 거쳐서 노드 4로 가는 경로를 찾을 수 있어 (2 → 3 → 4)
노드 3에서 출발하면 → 노드 5로 가는 경로를 찾을 수 있어 (3 → 5)

각 노드에서 출발하면서 새로운 최단 경로가 발견될 가능성이 높아짐

이렇게 하면 INF였던 값들이 대부분 채워짐

🔹 3. 그럼 모든 INF를 완전히 없앨 수 있을까?

💡 하지만! 그래도 모든 INF를 완전히 없앨 수는 없음

왜냐하면, 주어진 그래프에서 애초에 연결이 불가능한 노드 쌍이 있을 수도 있기 때문.

만약 그래프가 연결 그래프(Connected Graph) 라면,

즉, 어떤 노드에서든 다른 모든 노드로 가는 경로가 존재한다면 다익스트라를 반복 실행하면 모든 INF가 사라짐.

하지만 연결되지 않은 노드(Disconnected Node)가 존재하는 그래프라면,

즉, 아예 경로가 없는 노드 쌍이 있다면,

아무리 다익스트라를 여러 번 실행해도 INF는 남아 있음.

🔹 4. 모든 INF를 완전히 없애려면? (플로이드-워셜 알고리즘 사용)

만약 모든 INF를 없애고 모든 노드 쌍 간 최단 거리를 구하고 싶다면,

다익스트라 대신 플로이드-워셜 알고리즘을 사용하면 됨.

✅ 플로이드-워셜 알고리즘은

모든 노드 쌍 에 대해 최단 거리를 계산하는 알고리즘.

(다익스트라는 한 개의 출발 노드에서 모든 노드까지의 최단 거리만 구함.)

💡 플로이드-워셜을 사용하면, 모든 INF가 가능한 한 최단 거리 값으로 변환됨!

단, 그래프가 애초에 Disconnected Graph(완전히 연결되지 않은 그래프) 라면 플로이드-워셜을 사용해도 INF는 남아 있음! 🚨

🔹 5. 정리

방법	INF가 줄어드나?	완전히 없어지나?
다익스트라(한 번 실행)	일부 INF 줄어듦	여전히 INF 남음
다익스트라(모든 노드에서 실행)	더 많은 INF 줄어듦	그래프가 연결되어 있으면 대부분 없어짐
플로이드-워셜 알고리즘	모든 가능한 경로 확인	그래프가 연결되어 있다면 모든 INF가 사라짐

🚀 결론:

다익스트라를 여러 번 실행하면 INF가 줄어들지만 완전히 없어지지는 않을 수도 있다.
모든 INF를 없애려면 플로이드-워셜 알고리즘을 사용하는 게 가장 확실한 방법이다.

🔹 플로이드-워셜 알고리즘 개념

플로이드-워셜 알고리즘은 모든 노드 쌍 간 최단 거리를 구하는 알고리즘이야.

즉, 특정 출발점에서만 최단 거리를 구하는 다익스트라와 달리, 모든 노드에서 모든 노드까지의 최단 거리를 한꺼번에 구할 수 있어.

✅ 시간 복잡도: O(N³)** **(그래프의 크기가 커지면 느려질 수 있음)

✅ 기본 아이디어:

초기에는 직접 연결된 간선의 가중치만 사용해서 최단 거리 행렬을 만든다.
중간 노드를 하나씩 추가하며 최단 거리 행렬을 계속 업데이트한다.
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

import java.util.Arrays;

public class test7 { static final int INF = 99999999; // 무한대를 나타내는 값 static int[][] graph = { {0, 3, INF, 8, 9}, {3, 0, 2, INF, INF}, {INF, 2, 0, 1, 3}, {8, INF, 1, 0, INF}, {9, INF, 3, INF, 0} };

public static void floydWarshall(int n) { int[][] dist = new int[n][n];

// 초기 거리 행렬 복사 for (int i = 0; i < n; i++) { dist[i] = Arrays.copyOf(graph[i], n); }

// 플로이드-워셜 알고리즘 수행 for (int k = 0; k < n; k++) { // 중간 노드 k for (int i = 0; i < n; i++) { // 시작 노드 i for (int j = 0; j < n; j++) { // 도착 노드 j if (dist[i][k] != INF \&\& dist[k][j] != INF) { // 중간 노드가 유효한 경우만 업데이트 dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } }

// 최종 거리 행렬 출력 System.out.println(“모든 노드 쌍의 최단 거리 행렬:”); printMatrix(dist); }

public static void printMatrix(int[][] matrix) { for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { if (matrix[i][j] == INF) { System.out.print(“INF\t”); } else { System.out.print(matrix[i][j] + “\t”); } } System.out.println(); } }

public static void main(String[] args) { int n = 5; // 노드 개수 floydWarshall(n); } }

🔹 코드 설명

초기 그래프 설정
- INF 값을 사용해서 직접 연결되지 않은 노드는 무한대로 설정함.
플로이드-워셜 알고리즘 수행
- 3중 반복문을 사용해서 중간 노드를 하나씩 추가하며 최단 거리를 업데이트함.
- dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
- 중간 노드 k를 거쳐 가는 경로가 더 짧으면 업데이트.
최종 결과 출력
- INF 값이 사라지고 모든 노드 쌍의 최단 거리가 완성됨.

🔹 특징 및 장점

✅ 모든 노드 쌍의 최단 거리 계산 가능

✅ 음수 가중치도 사용할 수 있음 (단, 음수 사이클은 없어야 함)

✅ 그래프가 작은 경우(예: 노드 개수 100개 이하) 매우 효과적

❌ 시간 복잡도가 O(N³) 이므로, 노드 개수가 많아지면 느려질 수 있음

🚀 결론

다익스트라는 한 개의 출발 노드에서만 최단 거리를 구하는 알고리즘
플로이드-워셜은 모든 노드 쌍의 최단 거리를 한 번에 구하는 알고리즘
INF였던 값들이 모두 채워져서 완전한 최단 거리 행렬을 구할 수 있음!

🔹 시간 복잡도란?

시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간의 증가율을 나타내는 개념.

즉, 입력 크기(데이터 개수, n)가 커질 때, 실행 시간이 얼마나 증가하는지를 분석.

시간 복잡도는 보통 **빅-오 표기법(Big-O Notation)**을 사용해서 표현.

빅-오는 **최악의 경우(최대 실행 시간)**를 나타내므로, 코드의 성능을 평가하는 중요한 지표.

🔹 대표적인 시간 복잡도 예제

아래는 자주 등장하는 시간 복잡도와 예제를 정리한 표

시간 복잡도	의미	예제
O(1) (상수 시간)	입력 크기에 상관없이 실행 시간이 일정	배열에서 특정 인덱스 값 가져오기
O(log n) (로그 시간)	입력이 두 배가 되면 실행 시간은 조금만 증가	이진 탐색(Binary Search)
O(n) (선형 시간)	입력 크기만큼 실행 시간 증가	배열에서 최댓값 찾기
O(n log n)	O(n)과 O(log n)을 합친 형태	병합 정렬(Merge Sort), 퀵 정렬(Quick Sort)
O(n²) (이차 시간)	입력 크기가 커지면 실행 시간이 n²에 비례해 증가	중첩된 반복문 (버블 정렬, 선택 정렬)
O(n³) (세제곱 시간)	3중 반복문처럼 n³에 비례해 실행 시간 증가	플로이드-워셜 알고리즘
O(2ⁿ) (지수 시간)	입력이 조금만 증가해도 실행 시간이 엄청나게 증가	피보나치 재귀, 브루트포스
O(n!) (팩토리얼 시간)	가장 느린 알고리즘 (입력이 10만 되어도 실행 불가능)	외판원 문제(Traveling Salesman Problem)

🔹 시간 복잡도별 실행 속도 비교

만약 n = 10⁶ (1,000,000)일 때, 시간 복잡도에 따른 대략적인 실행 속도 비교

(1초에 약 10⁸번 연산할 수 있다고 가정)

시간 복잡도	n = 10⁶일 때 예상 실행 시간
O(1)	즉시 실행 (매우 빠름)
O(log n)	20번 이하의 연산 (매우 빠름)
O(n)	1,000,000번 연산 (괜찮음)
O(n log n)	약 2~3천만 번 연산 (괜찮음)
O(n²)	10¹²번 연산 (매우 느림)
O(n³)	10¹⁸번 연산 (실행 불가능)
O(2ⁿ)	n=30 정도에서만 실행 가능 (그 이상은 불가능)

🔹 플로이드-워셜의 시간 복잡도 O(n³)

플로이드-워셜 알고리즘의 시간 복잡도는 **O(n³)**

3중 for문을 사용하기 때문에 실행 시간이 n³에 비례해서 증가.
만약 n = 1000이라면, 1000³ = 10⁹번 연산해야 해서 매우 느려질 수 있음.
보통 n < 500 정도일 때만 실용적으로 사용! 🚀

🔹 정리

시간 복잡도는 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타냄.
빅-오 표기법(Big-O Notation)으로 표현하며, 최악의 경우를 기준으로 함.
O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(n³) → O(2ⁿ) 순으로 느려짐.
플로이드-워셜 알고리즘의 시간 복잡도는 O(n³)로, 큰 그래프에서는 비효율적일 수 있음.

댓글