플로이드 와샬 알고리즘

백준 문제를 풀면서 플로이드 와샬 알고리즘에 대해 궁금증이 생겨서 적어둔다! 플로이드 와샬 알고리즘이란? 그래프에서 모든 정점 간의 최단 경로를 찾는 알고리즘. 음의 가중치를 가지는 그래프에서도 동작하며, 그래프의 모든 정점 쌍 간의 최단 경로를 구하는데 사용된다. 다이나믹 프로그래밍 기법(DP)를 활용하여 문제를 효율적으로 해결한다. 기본 아이디어는 "거쳐가는 정점"을 기준으로 최단경로를 구하는 것이다. 동작 방식 초기화 : 그래프의 인접 행렬을 사용하여 최단 거리를 나타내는 2차원 배열을 초기화한다. 만약 두 정점 사이에 간선이 없으면 무한대(Infinity)로 설정. 중첩 반복문 : 모든 정점을 순회하여 해당 정점을 거쳐가는 경우를 고려한다. 최단 거리 갱신 : 현재 선택된 노드를 거쳐가는 경우와 ..

2023.07.26