플로이드 알고리즘(최단 경로)

🟩 모든 정점쌍에 대해서 둘 사이의 최단거리를 구할 수 있다.

cf. 다익스트라 : 한 시작점에서 다른 정점까지의 최단 거리

단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작

 

a 👉 b로 이동할 때, 경유점은 c

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

 

🟩 구현

 

1. 위의 그래프를 우선 배열로 구현해야 한다. 초기값은 아주 큰 값으로 설정해야 한다. 그리고 자기 자신까지의 비용은 0으로 설정한다.

 

2. 시작점을 i, 끝점을 j, 경유점을 k라 할 때, 구하는 식은 다음과 같다.

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

항상 작은 값만을 갖게 되므로 직접적으로 연결이 되지 않는 간선은 INF로 처음에 초기화한다.

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

EX) k=2일 때, adj[1][3] = MIN(adj[1][3], adj[1][2] + adj[2][3]) = MIN(INF, 6) = 6

 

👉 최종 비용 = 작은 값들을 더한 값

경유점 k의 순서가 꼭 0부터 V까지 순차적일 필요없다. 경유점은 어느 순서로 해도 상관없다.

 

🟩 시간복잡도

O(V^3)