공부한 내용 기록하기 공부한 내용 기록하기

1. 플로이드-워셜 알고리즘이란?플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘이다. 그래프의 각 정점에서 다른 모든 정점까지의 최단 경로를 효율적으로 계산하며, 음수 가중치를 허용하지만 음수 사이클이 존재하는 경우에는 사용할 수 없다.이 알고리즘은 동적 계획법(Dynamic Programming)을 기반으로 하며, 각 정점을 경유지로 활용해 최단 경로를 점진적으로 갱신한다.1.1 플로이드-워셜 알고리즘의 특징모든 정점 쌍의 최단 경로를 구함음수 가중치 허용 (음수 사이클은 감지 불가)동적 계획법을 활용한 최단 경로 갱신시간 복잡도: O(V³) (V는 정점의 수)2. 플로이드-워셜 알고리즘의 동작 원리플로이드-워셜 알고리즘은 다음과 ..