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 까지 하여 나온 행렬들이 최종 결과