목록최단경로 (1)

Meme's IT

[알고리즘] 플로이드 워셜, 그것이 알고싶다

최단 경로 알고리즘,마지막으로 플로이드 워셜 알고리즘을 알아봅시다!  # 플로이드 워셜 알고리즘이란?모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 최단 경로 알고리즘입니다.  다익스트라 알고리즘과의 비교다익스트라단계마다 최단 거리를 가지는 노드를 하나씩 선택해서, 경로를 확인하며 최단 거리 테이블을 갱신그리디 알고리즘플로이드 워셜단계마다 거쳐 가는 노드를 기준으로 알고리즘 실행DP 알고리즘즉, 플로이드 워셜은 최단 거리를 갖는 노드를 찾는 게 아니라, 거쳐가는 노드를 확인합니다.   # 플로이드 워셜 알고리즘의 시간 복잡도노드의 갯수가 N개 일 때, N번의 단계를 수행하며,단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려하므로총 시간 복잡도는 ..
SSAFY/그것이 알고싶다(기획) 2024. 1. 31. 00:16
이전 Prev 1 Next 다음