자료구조 & 알고리즘
[Algorithm/Java] 플로이드 - 워셜(floyd - warshall) 알고리즘 (최단거리)
플로이드 - 워셜(floyd - warshall) 알고리즘 플로이드 - 워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 시작점을 정해놓고, 해당 시작점에서 다른 모든 노드로의 최단거리를 구하는 다익스트라, 벨만-포드 알고리즘과 다르게 각각의 모든 노드에 대하여 다른 모든 노드로의 최단거리를 구할 수 있는 알고리즘이다. 모든 노드 간에 최단 경로를 탐색할 수 있다. 음수 가중치 간선이 있어도 수행할 수 있다. 동적 계획법을 이용하여 코드가 비교적 간단하다. 다른 알고리즘과 다르게 모든 노드사이의 최단거리를 도출하는 알고리즘이기 때문에 3중 for문을 이용한다. 시간 복잡도는 O( N^ 3)이다. 플로이드 - 워셜 알고리즘 동작 원리 1. 핵심 이론 2차원 배열에 모든 노드에 대하여 다른 모든 ..
