Computer Science/Algorithm
[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘
플로이드 와샬이란 모든 최단 경로를 구하는 알고리즘이다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라고 한다면, 플로이드-와샬은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있는 것이다. 다익스트라 알고리즘이 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다. 플로이드 와샬 알고리즘의 과정 예시로 모든 노드간의 최단거리를 구해야하므로 2차원 인접 행렬을 구성한다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복한다. 초기 그래프를 인접행렬로 나타내면 다음과 같습니다..
