플로이드-와샬1

• 

  210712 Matrix Multiplication , 플로이드-와샬(Floyd-Warshall 알고리즘) 모든 쌍의 최단 경로(All Pairs Shortest Path, ASP)의 대표적인 알고리즘 Matrix Multiplication 예시 플로이드-와샬(Floyd-Warshall 알고리즘) 거처가는 정점을 기준으로 최단 거리를 구하는 것 다익스트라,벨만-포드의 경우는 간선 하나씩 늘어나면서 계산, 반면 플로이드-와샬은 경유하는 정점이 하나씩 늘어나면서 계산 D : 그래프의 가중치를 담은 인접행렬 , 모든 쌍의 최단경로 비용 표시 π : 선행자 인접행렬 , 최단 경로 그 자체를 구할 때 사용 k 정점을 거쳤을 때 거리가 그대로거나 더 크다면 그대로 , 작아졌다면 값을 갱신 하는 과정 pseudo code 시간 복잡도 : O(n^3) 공간 복잡도 : O(n^2) 예시 정점의 개수 4 까지 하여 나온 행렬들.. 미가공 필기(알고리즘) 2021. 7. 13.