Floyd -Warshall Algorithm

📌 Floyd -Warshall Algorithm

그래프에서 모든 정점 쌍 간의 최단 경로를 한 번에 찾는 알고리즘입니다. 다익스트라(Dijikstra) 알고리즘이 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 것과 달리, Floyd-Warshall은 모든 정점 쌍에 대한 최단 경로를 구할 수 있습니다.
(음수 사이클이 없다는 가정 하에 음수 가중치가 있어도 최단 거리를 구할 수 있다는 장점)

# V는 정점의 개수
# dist[i][j]는 정점 i에서 j로 가는 최단 거리
for k in range(V):
    for i in range(V):
        for j in range(V):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

➡️ 시간 복잡도: O(V³)

🧹 정리
1) 정점들에 대한 연결 가중치를 담을 2차원 배열A와 최단거리 가중치를 담을 2차원 배열B를 선언
2) 3중 for문을 통해 직통(i,j)으로 가는 방법과 (i,k)에서 (k,j)로 가는 방법 중 가중치가 더 작은 수로 B배열을 업데이트 한다.

11403 경로찾기
위 문제에서는 가중치가 아닌, 단지 연결되어있음을 물어보는 문제이기 때문에 0 또는 1로 여부를 담아준다.

#include <iostream>
#include <string>
#include <queue>

#define MAX 101
using namespace std;
struct node{
  int x,y;
};
int dir[4][2]={
  0,1,
  1,0,
  0,-1,
  -1,0
};
int N ; 
int map[MAX][MAX];

void floydWarshall(int x, int y){
  
  int result[N+1][N+1] = {0};
  
  for(int i = 1 ; i <= N ; i ++ ){
      for(int j = 1 ; j <= N ; j ++ ){
        result[i][j] = map[i][j];
      }
  }
  
  
  for(int k = 1 ; k <= N ; k ++ ){
    for(int i = 1 ; i <= N ; i ++ ){
      for(int j = 1 ; j <= N ; j ++ ){
        if(result[i][k]  + result[k][j] > 1 )
            result[i][j] = 1 ;
      }
    }
  }
  
  for(int i = 1 ; i <= N ; i ++ ){
      for(int j = 1 ; j <= N ; j ++ ){
        cout<<result[i][j]<<" ";
      }
      cout<<'\n';
  }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 1 ; i <= N ; i ++ ){
        for(int j = 1 ; j <= N ; j ++ ){
          cin>>map[i][j];
        }
    }
  

    floydWarshall(0,0);

   
    return 0;
}

백준 참고 문제:
케빈 베이컨의 6단계 법칙
플로이드
키 순서