대학원생 신짜오는 공부중

이번에 해결한 알고리즘 문제는Find the Hub이다  sssp (single-source shortest path)와apsp (all-pair shortest path)를 이용해서city들 중에서 hub city를 찾는 알고리즘 문제이다 문제에서 찾아야하는 hub city는주어지는 distance threshold 이하의 거리로가장 많은 도시들을 연결하는 city이다   이번 문제의 자세한 설명은 위와 같다input으로는 총 3개가 들어오는데도시의 개수인 ndouble array 형식의 edges그리고 distanceThreshold가 들어온다 위 예시의 경우 city1은 총 3개의 도시를 threshold보다 같거나 작은 거리로 연결하고city2도 동일하게 3개의 도시를 threshole보다 같거나..

이 게시글은서울대학교 데이터사이언스대학원조요한 교수님의데이터사이언스 응용을 위한 컴퓨팅 강의를학습을 위해 재구성하였습니다.이번 시간은 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..