플로이드 알고리즘

플로이드 알고리즘은 모든정점에서 모든정점 까지의 최단경로를 구할 수 있는 알고리즘이다. 정점 출발점과 정점 목적지가 있을 때 그사이에 존재하는 정점들이 기준이 되러 최단 경로인 것을 경로로 만들어 주는 알고리즘이다. 구현 방법 또한 간단하다.

처음 배열을 갈 수 없는 길  INF(무한대) 갈수 없는 길로 표기 해준다음에 갈수 있는 길을 받은 자료를 이용하여 길을  계속 갱신해주면서 지나갈 수 있는 길을 만들어 주는 알고리즘이다. 다익스트라 알고리즘 경우에는 하나의 출발 정점 하나에서 모든 정점까지의 최단경로를 구할 수 있다. 그러나 플로이드 알고리즘 경우에는 모든 정점에서 모든 정점 까지의 최단 경로를 구할수 있다.  어떤 상황이 주어졌을 때 그때마다 어떤 방법이 적절하지 골라 사용하자.

 

 

 
    for(  k = 1 ; k<= N; k++) // 거쳐가는 정점
        for( i = 1 ; i<= N ; i++) // 출발 정점
            for( j = 1 ; j<=N ; j++) //도착정점
                if(map[i][j]  > map[i][k] + map[k][j]  )
                        map[i][j]  =  map[i][k] + map[k][j];
 

 

플로이드 모음

https://www.acmicpc.net/problem/tag/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C%20%EC%99%80%EC%83%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드 와샬 알고리즘 - 1 페이지