[알고리즘] Floyd-Warshall 알고리즘

모든 최단 거리를 구하는 방법 all pairs shortest path problem

 

그래프 종류: weighted, directed graph G = (V,E)

이때 weight func w: E->R (R은 실제 weight값, edge에 weight를 매핑한다.)

 

경로 p의 weight w(p)는 

 

특징

1. 음의 가중치를 가진 간선 사용가능 (다익스트라는 음의 가중치 간선 불가)

2. 자료구조는 2차원 배열 사용

3. optimal substructure 개념 사용

4. 시간복잡도 O(V^3)

 

*optimal substructure 

최단 경로 p내에 있는 정점 사이의 path도 모두 최단 경로이다. -> dp사용

 

 

초기화

거리를 저장하는 배열 dis[i][j] = c : i에서 j까지 비용이 c

모든 거리를 INF로 초기화 dis[i][j] = INF

 

++ 경로 역추적에 사용되는 배열 path[i][j] = k : i에서 j를 갈 때 k를 거친다.

로직

for(int k=1; k<=n; k++){
	for(int i=1; i<=n; i++){
    	for(int j=1; j<=n; j++){
        	dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

 

 

중간 경로를 1부터 5까지 추가하기

경로 확인 

if V(i->k)!=0 && V(k->j) !=0, then 경로 update 가능

추가했을 때 D값이 더 작아진다면 update

만약 값이 달라졌다면 P[[i][j] = k로 udpate

 

 

pseudo code

void floyd-warshall()
{
    
    for k = 1 to row_num 
    {
    	for i = 1 to row_num
        {
        	for j = 1 to row_num 
            {
            	distance[i][j] = min(distance[i][j], distance[i][k]+distance[k][j])
             }
         }
    }
 
}