[Java] 플로이드 워샬

1. 플로이드 워샬이란? 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘.시간복잡도 : O(N^3) Dijkstra와 달리 모든 노드 쌍에 대한 최단 거리를 구하고,음의 가중치를 가지는 그래프에서도 쓸 수 있다! 2. 구현 DP로 접근하기 위해 부분 문제를 정의해야 한다. s에서 e까지 가는 데 걸리는 최단거리는 (s->e) 또는 (s->m→e)이다.(s->m→e) = s에서 m까지 가는 데 걸리는 최단거리 + m에서 e까지 가는 데 걸리는 최단거리 int INF = 1000000; // 도달할 수 없음을 의미 (구체적인 값은 문제 따라서 다름)int[][] graph; // 그래프를 나타내는 2차원 배열int n; // 노드의 개수public void floydWarshall() { //..

2024.06.13