Floyd 알고리즘이란 무엇인가?

플로이드(Floyd) 알고리즘

플로이드 알고리즘 : 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구한다.

다익스트라 알고리즘 : 한 시작점에서 다른 정점까지의 최단 거리를 구한다.

1) 경유점

• a와 b로 연결되어 있는 간선의 비용 : 5
• a와 c : 2, c 와 b : 2 => 4

a와 b로 가는데 c를 거쳐가는 것이 더 효율적이다.

c와 같이 경로가 거쳐가는 정점이 경유점이라고 한다.

플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 된다.

2) 구현

위 그래프가 있을 때, 모든 쌍의 최단거리는 어떻게 될까?🤔

다익스트라 알고리즘을 이용하여 모든 정점에 대해서 구할 수 있지지만, 플로이드 알고리즘을 쓰면 보다 쉽고 빠르게 구할 수 있는 장점이 있다.

2-1) 그래프의 초기화

• 배열로 구현해야 한다.
• 초기에 직접적으로 연결되어 있지 않은 경로는 큰 값으로 설정해야 한다.
• 1 <-> 1와 같이 자기 자신 비용은 0으로 둔다.

2-2) 플로이드 알고리즘 적용

• 시작점 : i
• 끝점 : j
• 경유점 : k

adj[i][j]=MIN(adj[i][j], adj[i][k]+adj[k][j])

이 경유점 k를 지나는 모든 i, j에 대해서 확인해주면 된다.

ex)

1) 먼저 adj[1][2]=MIN(adj[1][2], adj[1][0] + adj[0][2]) = MIN(INF, 5) = 5 일 때

2) 다음 차례 adj[1][3] = MIN(adj[1][3], adj[1][2] + adj[2][3]) = MIN(INF, 6) = 6이다.

이와 같이 모든 경유점을 확인하면서 비용이 작은 값만을 선택하면 된다.

3) 결론

플로이드 알고리즘

• 1 ~ n 까지 start 노드로 잡고 다익스트라를 수행하는 것이다.
• 시간을 많이 잡아먹지만, 노드 개수가 적은 경우 유용한 알고리즘이다.

참고자료

• https://reakwon.tistory.com/55