플로이드 와샬

플로이드 와샬 알고리즘은 다익스트라 알고리즘과 같이 최단 거리를 구할 수 있는 알고리즘이다.

다익스트라

• 정해진 하나의 출발점에서 가장 적은 비용을 선택해서 다른 모든 정점까지의 최단 경로를 구한다.
• 우선순위 큐를 사용한다

플로이드 와샬

• 모든 정점 간의 최단 경로를 구한다.
• 모든 쌍을 표현할 수 있는 이차원 배열을 선언하고,
  다이나믹 프로그래밍 방식으로 원소 간 최단 거리를 업데이트한다.
• 매번 행렬 전체 원소들에 대해 갱신을 진행한다.

'경로 찾기'

BOJ '경로 찾기' 문제 보러가기

풀이 코드

플로이드 와샬 알고리즘의 기본 원리를 이용하면 쉽게 풀 수 있는 문제이다.

#include <iostream>
using namespace std;
int N;
int graph[105][105], answer[105][105];

void printGraph(){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cout << graph[i][j]<<' ';
        }
        cout << '\n';
    }
}

int main() {
    // 1. 입력받기
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> graph[i][j];
        }
    }

    // 2. 경유 지점의 변화에 따라 모든 경우를 업데이트
    for(int k=0;k<N;k++){ // 경유 지점
        for(int i=0;i<N;i++){ // 시작점
            for(int j=0;j<N;j++){ // 도착점
                // (1) 곧장 연결되거나 (2) 경유해서 연결할 수 있거나
                if(graph[i][j] == 1 || (graph[i][k] == 1 && graph[k][j] == 1)){
                    graph[i][j] = 1;
                }
                
            }
        }
    }

    // 3. 정답 출력
    printGraph();    
}

참고 자료

• (C++) 플로이드 와샬 Floyd Warshall (+ 최단 경로 알고리즘 비교)