floyd's algorithm1 [알고리즘 분석] - Graph Algorithm_Floyd's Algorithm for All-Pairs Shortest Paths 이전 글에서는 Dijkstra's Shortest-path Algorithm 방식에 대해서 정리해 보았다. 이번 글에서는 플로이드의 알고리즘을 통해 그라프의 최단 경로를 찾는 방법에 대해 정리해 볼 예정이다.1. Adjacency matrix 플로이드의 알고리즘에 대해서 정리하기 전에, 플로이드 알고리즘의 기본 아이디어 예시를 한 번 살펴보려고 한다. 예시 그라프에 대해 다음 인접 행렬이 존재한다고 가정해보자.위의 인접 행렬 A는 각 vertex에 경로가 존재하면 1, 아니면 0으로 표시한 Boolean matrix이다. 따라서 이 행렬의 곱셈은 logical 연산을 통해 수행 되는데, 이를 이용해 A^2과 A^3을 구하면 다음과 같다. 이때, A^2의 행렬을 통해 그라프를 다시 그려보자. 그럼 다음과 .. 2025. 6. 13. 이전 1 다음
