목록2025/02/27 (1)

데이터 분석 기술 블로그

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘"그래프에서 모든 노드 간 최단 경로를 한 번에 구하는 알고리즘"음수 간선도 처리 가능 (음수 사이클은 처리 불가!)모든 노드에서 모든 노드까지의 최단 경로를 한 번에 계산동적 계획법(DP) 기반으로 O(V³)의 시간복잡도를 가짐노드 개수가 작을 때 사용하기 적합플로이드-워셜 알고리즘 동작 원리모든 노드 간의 최단 거리를 저장하는 2차원 DP 테이블(행렬) 초기화모든 노드를 '경유지(K)'로 설정하면서 최단 경로 갱신테이블이 더 이상 갱신되지 않으면 종료# Pseudo CodeFUNCTION FloydWarshall(graph, V): 거리 = 그래프의 가중치 행렬 초기화 FOR k FROM 1 TO V DO: # 모든 노드를 경유지로 설정 FOR i FRO..
데이터 사이언스/알고리즘 2025. 2. 27. 18:37
이전 Prev 1 Next 다음