해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다.
- 한 지점에서 다른 특정 지점까지의 최단경로를 구해야 하는 경우
- 모든 지점에서 다른 모든 지점까지의 최단경로를 구해야하는 경우
종류
다익스트라 최단 경로 알고리즘
- 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘
- ex) 노드1 to 노드 2, 3, 4, 5
- 시간복잡도 : O(ElogV)
- 우선순위 큐 (heapq), distance 테이블 활용
플로이드 워셜 알고리즘
- 모든 노드에서 출발하여 모든 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘
- ex) 노드1, 2, 3, 4, 5 to 노드 1, 2, 3, 4, 5
- 시간 복잡도 : O(N**3)
- 3중 for문 사용
- 비교 대상
" A에서 B를 거쳐 C로 가는 경우 vs A에서 C로 바로 가는 경우"
