Floyd-Warshall 알고리즘

플로이드-워셜 알고리즘

플로이드-워셜 알고리즘은 그래프에서 모든 정점 쌍 간 최단경로를 찾는 알고리즘입니다. 음의 가중치를 가지는 간선에서도 동작할 수 있고, DP(Dynamic Programming) 기법을 사용해서 구현합니다.

동작 과정

1. 초기 그래프의 인접 행렬 생성. 인접 행렬은 정점간 가중치를 저장하는 2차원 배열. 가중치 없는 경우 INF로 초기화
2. 모든 정점 쌍에 대해 최단 거리 갱신. 3중 for문 사용
   • 외부 반복문 : 거쳐가는 중간 정점 선택
   • 중간 반복문 : 출발 정점 선택
   • 내부 반복문 : 도착 정점 선택, 최단 거리 갱신
3. 중간 정점을 거치는 경로가 더 짧으면, 최단 거리 갱신
4. 모든 정점 쌍에 대해 갱신이 안 된다면 알고리즘 종료
5. 최종적을 인접 행렬에 저장된 값은 정점 쌍 간의 최단 거리를 나타낸다.

pseudo-code

function FloydWarshall(graph):
    distance := adjacency matrix of the graph
    n := number of vertices in the graph

    // Initialize the distance matrix
    for each vertex u in the graph:
        for each vertex v in the graph:
            if u and v are adjacent:
                distance[u][v] := weight(u, v)
            else:
                distance[u][v] := INF (infinity)

    // Compute the shortest paths
    for each vertex k in the graph:
        for each vertex i in the graph:
            for each vertex j in the graph:
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] := distance[i][k] + distance[k][j]

    return distance

C++ 구현

#include <iostream>
#include <vector>

using namespace std;

const int INF = 1e9; // 무한대 값

void floydWarshall(vector<vector<int>>& graph) {
    int n = graph.size();

    // 최단 거리 행렬 초기화
    vector<vector<int>> distance(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            distance[i][j] = graph[i][j];
        }
    }

    // 최단 경로 계산
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (distance[i][j] > distance[i][k] + distance[k][j]) {
                    distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }
    }

    // 최단 거리 행렬 출력
    cout << "최단 거리 행렬:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (distance[i][j] == INF) {
                cout << "INF ";
            } else {
                cout << distance[i][j] << " ";
            }
        }
        cout << endl;
    }
}

int main() {
    int n; // 정점의 수
    cout << "정점의 수: ";
    cin >> n;

    vector<vector<int>> graph(n, vector<int>(n));

    cout << "그래프의 인접 행렬을 입력하세요:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> graph[i][j];
            if (graph[i][j] == -1) {
                graph[i][j] = INF; // 경로가 없는 경우 무한대 값으로 설정
            }
        }
    }

    floydWarshall(graph);

    return 0;
}

다른 알고리즘과 비교

	플로이드-워셜	벨만-포드	다익스트라
장점	모든 정점 쌍 간 최단 거리를 한 번에 계산 가능. 음의 가중치의 간선도 처리 가능 경로 추적을 위한 경로도 제공	음의 가중치의 간선도 처리 가능 음수 사이클 감지	시간 복잡도가 O((V+E)logV)로 빠르다. 그래프에서 음의 가중치를 가지는 간선이 없는 경우 적합
단점	시간 복잡도가 O(V^3)으로 계산량이 크다. 밀집 그래프에서 메모리 사용량이 많다.	시간 복잡도가 O(V*E)로 간선 수에 비해 계산량이 크다.	음의 가중치를 가지는 간선 처리 불가 시작 정점과 도착 정점 간의 최단 경로만 구할 수 있다.