플로이드 워셜1 [알고리즘 개념 정리] 플로이드 워셜 (Python) [이것이 코딩 테스트다 with Python] 31강 플로이드 워셜 알고리즘을 듣고 정리한 내용입니다. 플로이드 워셜 알고리즘 - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. - (다익스트라 알고리즘과 마찬가지로) 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만, 다익스트라 알고리즘과 달리 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이 필요하지 않다. - 2차원 테이블에 최단거리 정보를 저장한다. - 다이나믹 프로그래밍 유형에 속하며, 시간 복잡도는 O(n³)이다. - 노드의 갯수가 적은 경우에 사용이 적합하며, 노드와 간선의 갯수가 많은 경우에는 다익스트라 알고리즘을 활용해야하는 경우가 많다. 실제로도 .. 2024. 3. 25. 이전 1 다음