플로이드(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)인 반면,(알고리즘책에는 O(n^2)라고 나왔는데 제 생각에는 O(2n^2)이 더 정확한 것 같습니다.) 플로이드 알고리즘은 O(n^3)입니다. 시간 복잡도만으론 플로이드 알고리즘이 대체적으로 느릴 것 같으나, 다익스트라 알고리즘이 한번의 루프를 돌 때마다 하는 일이 많다보니(복잡하다보니) 실제로는 플로이드가 빠른 경우가 상당히 많습니다. 그래서 저는 플로이드 알고리즘을 좋아합니다^^; 다익스트라는 강좌를 썼음에도 불구하고.. 복잡해 보여요..TT 암튼 플로이드 알고리즘은 위에 처럼 3중 for문을 돌면서 i->j로 가는 거리보다 i->k->j로 가는 거리가 짧을 때마다 갱신하는 것입니다. a[i,j] = i에서 j로 가는 최단거리 라는 것을 알고 다익스트라 알고리즘이 이해 되셨다면 더 이상 설명이 필요없을 것 같네요. 그럼 다익스트라 알고리즘에서 썼던 그래프를 가지고 최단거리를 구해봅시다.
program Floyd; const n=8; m=5000; data:array[1..n,1..n] of integer= ( (0,2,m,m,m,3,m,m), (2,0,4,1,m,m,m,m), (m,4,0,m,m,m,3,m), (m,1,m,0,3,m,2,m), (m,m,3,3,0,m,m,4), (3,m,m,m,m,0,6,m), (m,m,m,2,m,6,0,4), (m,m,m,m,4,m,4,0)); var k,i,j: integer; begin 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]; for i:=1 to n do for j:=1 to n do writeln(i,'=>',j,' : ',a[i,j]); end.