경유가능한 점이 4일 때의 AllPairsShortest 알고리즘 수행 과정

소개글

"경유가능한 점이 4일 때의 AllPairsShortest 알고리즘 수행 과정"에 대한 내용입니다.

목차

1. All-pair Shortest Paths 알고리즘
2. 시간복잡도
3. 작동 원리
4. 예시(진행과정)
5. 답안
6. 마치며

본문내용

1. All-pair Shortest Paths 알고리즘

All-pair Shortest Paths 알고리즘은 모든 정점을 출발점으로 고려하여 모든 정점에 대한 최단 경로를 구하는 알고리즘이다.
대표적인 All-pair Shortest Paths 알고리즘들은 Floyd-Warshall 과 Shortest Paths and Matrix Multiplication 알고리즘이 있는데둘다 인접행렬을 이용하여 구현할 수 있지만 수업시간에 배운 Floyd-Warshall 알고리즘을 이용하도록 하겠다.

2. 시간복잡도

Floyd-Warshall 알고리즘의 시간복잡도는 O(n^3)이다.
Dijkstra 알고리즘을 (n-1)번 사용할 때 시간복잡도와 동일하며, 각 경유 가능한 점에 대하여 모든 i, j 쌍에 대하여 계산되기 떄문이다.

3. 작동 원리

Floyd- Washall 알고리즘은 동적 계획법(Dynamic Programming) 기술을 이용한다.

참고 자료

강의 교안
티스토리, "Floyd-Warshall 알고리즘”, https://engkimbs.tistory.com/371 , 2020.05.11.
티스토리, "floyd warshall all pairs shortest path algorithm”, https://victorydntmd.tistory.com/106 , 2020.05.11.