[펌] 플로이드 알고리즘
플로이드(Floyd) 알고리즘플로이드(Floyd) 알고리즘도 다익스트라 알고리즘처럼 최단거리를 구하는 알고리즘입니다. 다른 점은 다익스트라 알고리즘이 한 점에서 출발해서 각 정점에 최단거리를 구하지만, 플로이드 알고리즘은 모든 점점에서 출발해서 출발 한 정점을 제외한 모든 정점을 도착점으로 하는 최단거리를 구하는 알고리즘입니다. 플로이드 알고리즘의 대략적인 코딩은 다음과 같이 합니다.for k:=1 to n do for i:=1 to n do for j:=1 to n do if a[i,j] > a[i,k] + a[k,j] then a[i,j] := a[i,k] + a[k,j];보시다시피 다익스트라 알고리즘보다 코딩이 훨씬 간단합니다. 다익스트라 알고리즘의 시간복잡도가 O(2n^2)인 반면,(알고리즘책에는..