플로이드-와샬 알고리즘(11404 플로이드)

플로이드-와샬 알고리즘

다익스트라 알고리즘이 한 정점에서 모든 정점까지의 최단거리를 구해주는 알고리즘이라면

플로이드-와샬 알고리즘은 모든정점에서 모든정점으로의 최단거리를 구해주는 알고리즘이다.

다이나믹 프로그래밍을 기반으로 거쳐가는 정점을 기준으로 한다는 특징이 있다.

 

다익스트라와 다른점은 다익스트라는 힙을 이용하여 일차원 배열에 값을 나타냈으므로 입력을 받을 때

adj[시작점]=(가중치,목적지)를 받았다면 플로이드는 2차원배열 adj[시작점][목적지]=가중치로 저장한다는 차이가 있다.

 

임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다.

식으로 설명해보자면 현재의 table에서 adj[s][e]보다 adj[s][m]+adj[m][e]가 작다면 갱신해준다는 뜻이다.

 

처음봤을때는 이렇게하면 놓치는 부분이 많을 것이라고 생각했지만 for문을 3번돌리면서 맨위 for문에 거쳐가는 정점 k를 기반으로 계속 돌리므로 모든 경우의 수를 돌았다. 즉 시간이 오래걸리는 알고리즘이다.

시간복잡도는 O(n^3)로 문제에서 n이 너무크다면 다른방법을 써야한다.

 

플로이드 대표문제로 코드를 보자.

 

플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

1.접근

n이 100밖에 되지않고 모든도시의 쌍을 구하라고 한다. 당연히 플로이드 알고리즘을 적용해야한다.

 

2.풀이

우선 모든 입력을 받아서 배열에 집어넣어야 한다. 여기서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 조건이 있어서 배열에는 항상 최솟값이 들어가야 한다.

배열을 채운후에는 플로이드 알고리즘을 적용하면 끝난다. 출발점과 시작점이 같은 곳은 0으로 바꿔준다. 또 길이 없는 경우 INF값일 것이므로 0으로 바꿔준다.

 

3.코드

 

4.배운점

• i==j일 때 0으로 초기화 하지않으면 자기 자신으로 돌아오는 최단거리도 구할 수 있다

• 놓치는 경우가 있을거라고 생각했지만 없었다. 알고리즘을 의심하지말자