개발일지

개념 Floyd Warshall (플로이드 와샬) 알고리즘은 정점과 정점 사이의 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 특징은 모든 정점 사이의 거리를 구할 수 있다. 최단 경로를 찾을 때 중간에 한번 거쳐서 가는 경로 중 가장 가까운 경로로 업데이트 하면서 모든 정검들의 최단 거리를 구하는 알고리즘이다. 시간 복잡도가 O(V^3)이라는 꽤 오래 걸리는 알고리즘 이지만 모든 정점 사이의 최단 거리를 구할 수 있다. 작동원리 1. 중간 정점 K, 시작 정점 I, 도착 정점 J로 삼중 반복문을 순회한다. 2. distance[i][j]가 distance[i][k] + distance[k][j]보다 크면 경로를 업데이트 한다. -> distance[i][k], distance[k][j]가 ..