이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간은 apsp의 두번째 강의 내용을 정리해보려고한다내용은 Floyd-Warshall Algorithm과Johnson Algorithm이다 Floyd-Warshall Algorithm Floyd-Warshall Algorithm의 가정은 아래와 같다negative weight는 존재하지만 negative weight cycle은 존재하지 않는다 time complexity는 O(V세제곱)이 소요되고dynamic programming(dp)를 이용해서 해결하는 알고리즘 중 하나이다 최적해를 찾는 구조를 살펴보자우선 그래프G가 있다고 할 때 모든 vertex들을1부터 n까지 numb..
