[Algorithm] Floyd-Warshall Algorithm

알고리즘 문제를 풀다가 최소 비용 문제와 관련하여 플로이드 워셜 알고리즘을 알게되어 정리해 본다.

 

💡알고리즘 설명

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

그래프 - 나무위키

플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다.

조금 더 구체적인 설명을 위해, 임의의 노드 s 부터 e 까지 가는데 걸리는 최단거리를 d[s][e]라고 하자. (처음에 d[s][e]의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.[2]) 이 d[s][e]를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재 d[s][e]에 저장되어 있는 값과, d[s][m]+d[m][e]의 값을 비교한다. 이 때 d[s][m]+d[m][e]의 값이 현재의 d[s][e] 값보다 작으면, d[s][e]를 d[s][m]+d[m][e] 의 값으로 업데이트한다.

 

구현 코드는 3중 for문으로 간단하다.

for(m=1; m<=N; m++){
    for(s=1; s<=N; s++){
      for(e=1; e<=N; e++){
      	if(s==m || s==e || m==e) continue;
        if (d[s][m] != INF && d[m][e] != INF)
        	d[s][e] = min(d[s][e], d[s][m] + d[m][e]);
        }
     }
 }

N : 노드의 개수

m : 중간점

s : 시작점

e : 도착점 

 

시작점->도착점으로 바로가는 거리보다 시작점 -> 중간점 -> 도착점으로 가는 비용이 더 적게 든다면 d[s][e]를 갱신해준다. 이때 시작점과 도착점이 동일한 (1,1) 와 같은 지점은 pass한다. 이 과정을 반복한다.

 

---

💻관련문제

합승택시요금 : programmers.co.kr/learn/courses/30/lessons/72413