플로이드1 플로이드(Floyd) 알고리즘 0. Intro 자료구조 수업 때 그래프 부분에서 다익스트라 알고리즘에 대해 배운 적이 있습니다. 다익스트라 알고리즘 경우에는 한 시작점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이었습니다. 이번에는 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 플로이드 알고리즘에 대해 소개해보겠습니다. 개인적으로 다익스트라 알고리즘보다 훨씬 이해하기는 쉬운 알고리즘 같습니다. 단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서만 유효한다는 것을 주의해야 합니다. 1. 플로이드(Floyd) 알고리즘 플로이드 알고리즘은 동적 계획법(Dynamic Programming) 기법을 사용합니다. 이를 위해서는, 그래프의 인접 행렬(adjacency matrix)을 이용하여 모든 정점 쌍 사이의 최단 경.. 2023. 4. 7. 이전 1 다음
