[알고리즘] 플로이드 - 워셜(Floyd-Warshall)

 

11404번: 플로이드

 

 

Floyd-Warshall은 최단 경로 알고리즘의 일종이다. (ft. Dijkstra, Kruskal, Prim)
- 시간 복잡도는 O(N^3)이 걸리기 때문에, N의 값이 작을 때만 사용하도록 한다.
- 다른 알고리즘과는 다르게 음의 값도 사용할 수 있다.
- 모든 노드의 최단 경로를 찾을 수 있다. ( 다른건 한 노드에서 다른 노드까지...)

 

최단 경로 알고리즘

 

플로이드 - 워셜 (Floyd-Warshall) 알고리즘

 

=> 다익스트라는 하나의 정점 ~ 다른 모든 정점까지 거리를 구하는 알고리즘이라면, 플로이드 워셜은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다. 

* 플로이드 - 워셜 알고리즘은 다익스트라와 다르게 음의 간선도 사용할 수 있음

 

---

 

동작 과정

모든 노드 간 최단거리를 구해야 하므로 2차원 인접 행렬을 구성한다. 알고리즘은 여러 라운드로 구성되며 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택해 줄이는 과정을 반복한다.

 

위와 같은 그래프가 있을 때, 2차원 행렬에 인접행렬을 나타낸다. 

0	5	INF	9	1
5	0	2	INF	INF
INF	2	0	7	INF
9	INF	7	0	2
1	INF	INF	2	0

 

1. 1번 노드를 새로운 중간 노드로 설정한다. 

그래프는 1~5번 노드가 있어 알고리즘은 총 5라운드의 과정을 거친다.

=> 모든 노드들을 중간 노드로 선정하는 과정을 거친다.

 

1번 노드를 중간노드로 선정할 경우, 2->4의 길은 원래 없었지만 2-1-4가 가능해진다. 

(갱신 된 인접 행렬은 노란색)

0	5	INF	9	1
5	0	2	14	6
INF	2	0	7	INF
9	14	7	0	2
1	6	INF	2	0

 

2. 2번 노드를 새로운 중간 노드로 설정

 

1번을 반복한다.

 

---

 

구현

1. adj에 저장된 인접 행렬의 값을 활용해 최단 거리 배열인 dist 배열을 초기화 한다. 

for(int i=1; i<=N; i++){
	for(int j=1; j<=N; j++){
    	// i=j인경우 = 0
    	if(i==j) dist[i][j] = 0; 
        // 인접 행렬 값이 있으면 갱신
        else if(adj[i][j]) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

 

2. 각 라운드 별로 중간 노드가 될 노드 번호를 for 문 가장 바깥의 k로 삼는다. 내부 이중 for문에는 i,j를 통해 각 노드별 모든 거리를 살펴보며 k를 중간 노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 업데이트 한다.

//중간 노드를 선택하는 for 문
for(int k=1; k<=N; k++){
	//전 노드 선택
	for(int i=1; i<=N; i++){
    	// 다음 노드 선택
        for(int j=1; j<=n; j++){
        	// i->j까지 가는 방법 = min(원래 있던, 중간노드 k를 거쳐 가는 방법)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}