on
7. 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall)
7. 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall)
728x90
플로이드 워셜 알고리즘
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행 한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
한다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.
노드의 갯수가 적은 경우에서 효과적으로 사용할 수 있으며, 노드 및 간선의 개수가 많은 경우에는 일반적으로 다익스트라 알고리즘을 사용해야하는 경우가 많다.
플로이드 워셜 알고리즘
각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인 한다. a에서 b로 가는 최단 거립다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
한다. 점화식은 다음과 같다.
플로이드 워셜 알고리즘: 동작 과정
[초기 상태] 그래프를 준비하고 최단 거리 테이블을 초기화한다. 기본 점화식: Dab = min(Dab, Dak + Dkb)
[Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. 점화식: Dab = min(Dab, Da1 + D1b)
[Step 2] 2번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. 점화식: Dab = min(Dab, Da2 + D2b)
[Step 3] 3번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. 점화식: Dab = min(Dab, Da3 + D3b)
[Step 4] 4번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. 점화식: Dab = min(Dab, Da4 + D4b)
플로이드 워셜 알고리즘
플로이드 워셜 문제는 노드의 개수가 500개가 안넘도록 설정하는 경우가 많다.
public class FloydWarshall { private static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 의미 // 노드의 개수 (N), 간선의 개수 (M) // 노드의 개수는 최대 500개라고 가정 private static int n, m; // 2차원 배열(그래프 표현)를 만들기 private 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 i = 1; i <= n; i++) { graph[i][i] = 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; a++) { 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 "); continue; } System.out.print(graph[a][b] + " "); } System.out.println(); } } }
플로이드 워셜 알고리즘 성능 분석
노드의 개수가 N개일 때 알고리즘상으로 N번의 단계를 수행한다. 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다.
따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.
728x90
from http://rok93.tistory.com/183 by ccl(A) rewrite - 2021-08-20 20:00:18