플로이드 워셜 알고리즘

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. DynamicProgramming 기술에 의거한다.

 

"거쳐가는 정점"을 기준으로  최단거리를 구한다.

 

코드는 단순히 반복문을 3번 중첩시키기만 하면 되기 때문에 구현에 있어 크게 어려운 부분은 없다.

단, 유의하여야 할 점은 for문에서 가운데 노드(m)이 제일 위에 있어야 한다는 점이다.

 

시간복잡도는 O(V^3)O(V3)이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다.

 

플로이드워셜 갱신

1을 거쳐가는 경우를 갱신한다 하면

=> D[2,3] 과 ( D[2,1] + D[1,3] ) 을 비교하여 최솟값으로 업데이트한다.

=> min( 9, 7+inf) = 9

 

이러한 방식대로 업데이트하면 된다.

 

 

아래는 플로이드 워셜을 구현한 c코드이다.

for(m=1; m<=N; m++)
    for(s=1; s<=N; s++)
      for(e=1; e<=N; e++)
        if (d[s][e] > d[s][m] + d[m][e])  
        	d[s][e] = d[s][m] + d[m][e];
       

 

출처 :m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F

24. 플로이드 와샬(Floyd Warshall) 알고리즘

namu.wiki/w/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 나무위키