플로이드 와샬 알고리즘

다익스트라와 벨만-포드 알고리즘은 시작점이 정해져 있어서 모든 쌍에 대한 최단 경로를 알아낼 수 없었습니다.

 

물론, 단일 시작점 알고리즘을 여러 번 돌린다면 모든 쌍에 대한 최단 경로를 찾아낼 수 있지만, 시간 복잡도와 알고리즘 구현 측면에서 한번만 실행해도 되는 플로이드-와샬 알고리즘이 더 적합한 선택일 것입니다.

 

2020/08/31 - [알고리즘] - 다익스트라 알고리즘

2020/09/07 - [알고리즘] - 벨만포드 알고리즘

2020/09/07 - [알고리즘] - SPFA (Shortest Path Faster Algorithm)

 

플로이드-와샬 알고리즘은 벨만-포드 알고리즘과 동일하게 음수 가중치가 있어도 사용 가능합니다.

 

 

플로이드-와샬 알고리즘의 동작 과정을 알아봅시다.

---

먼저, 모든 쌍의 최단 경로의 길이를 저장할 2차원 배열을 생성합니다.

주어진 간선은 배열에 적용을 하고, 자기 자신으로의 거리는 0, 주어지지 않은 간선은 Max 로 설정합니다.  

 

플로이드-와샬 알고리즘은 이전에 소개해드린 알고리즘과는 약간 다른 방식으로 전개됩니다.

한 정점에서 다른 정점으로의 최단 경로의 길이가, 중간에 경유점을 지나서 갈 때보다 길다면 경로를 갱신합니다.

 

1번 정점을 경유점으로 설정합니다.

모든 정점 쌍에 대하여 최단 경로가 1번 정점을 경유한 경로보다 크다면 최단 경로를 갱신합니다.

갱신할 경로가 없습니다.

 

 

2번 정점을 경유점으로 설정합니다.

모든 정점 쌍에 대하여 최단 경로가 2번 정점을 경유한 경로보다 크다면 최단 경로를 갱신합니다.

 

3번 정점을 경유점으로 설정합니다.

모든 정점 쌍에 대하여 최단 경로가 3번 정점을 경유한 경로보다 크다면 최단 경로를 갱신합니다.

 

4번 정점을 경유점으로 설정합니다.

모든 정점 쌍에 대하여 최단 경로가 4번 정점을 경유한 경로보다 크다면 최단 경로를 갱신합니다.

갱신할 경로가 없습니다.

 

5번 정점을 경유점으로 설정합니다.

모든 정점 쌍에 대하여 최단 경로가 5번 정점을 경유한 경로보다 크다면 최단 경로를 갱신합니다.

 

...

 

이렇게 모든 정점을 경유점으로 설정을 하고 모든 정점 쌍에 대한 최단 경로를 갱신했다면 알고리즘이 종료가 됩니다.

 

만약 자기 자신으로 가는 최단 경로의 길이가 음수인 정점이 생겼다면 그래프 내에 음수 사이클이 존재한다는 증거입니다.

 

 

이제 플로이드-와샬 알고리즘을 소스코드로 알아봅니다.

---

int V,E,u,v,w;

int adj[V_Max][V_Max];
//메인함수에서 간선을 저장할 2차원 배열을 만들어놓습니다.

void floyd(){

  for(int i=0; i<V; i++)
    for(int j=0; j<V; j++)
      adj[i][j] = MAX;
  //서로 간선이 없는 모든 정점 쌍에 대하여 최단 경로의 길이를 MAX로 초기화 합니다.
 
  for(int i=0; i<V; i++) 
  	adj[i][i] = 0;
  //모든 정점은 자기 자신으로의 최단 경로의 길이가 0 입니다.

  for(int k=0; k<V; k++)
    for(int i=0; i<V; i++){
    
    	if(adj[i][k]==MAX) continue;
        //시작점에서 경유점으로 가는 경로가 MAX라면 굳이 체크할 필요가 없습니다.
        //체크를 하지 않으면 이후에 |V|만큼 불필요하게 탐색하는 것을 막을 수 있습니다.
        
    	for(int j=0; j<V; j++)
        	adj[i][j] = min(adj[i][j],adj[i][k]+adj[k][j]);
        //시작점에서 도착점으로의 최단 경로의 길이가 경유점을 지나서 가는 것보다 길다면 갱신합니다.
            
        }
  
   
}

 

---

플로이드-와샬 알고리즘의 시간 복잡도

 

V에 대한 3중 for문을 사용했으므로 플로이드-와샬 알고리즘의 시간 복잡도는 O(|V|^3) 이 됩니다.

---

연습문제

 

2020/08/29 - [백준] - 백준 소스코드 [C++] 11404 플로이드

2020/08/29 - [백준] - 백준 소스코드 [C++] 11403 경로 찾기

 

최단 경로 알고리즘 중 플로이드-와샬 알고리즘에 대한 포스팅이었습니다.

오타 지적과 조언은 언제나 환영입니다.