[C++로 배우는 알고리즘과 자료구조] Day 26: 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

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

플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치가 있는 그래프에서도 작동하지만, 음의 사이클이 있는 그래프에서는 사용할 수 없습니다.

플로이드-워셜 알고리즘의 시간 복잡도:

• (O(V^3)), 여기서 (V)는 정점의 수입니다.

플로이드-워셜 알고리즘 구현

그래프 구현 (인접 행렬 사용)

#include <iostream>
#include <vector>
#include <climits>

// 무한대 값을 나타내는 상수
const int INF = INT_MAX;

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v, int weight); // 간선 추가
    void floydWarshall(); // 플로이드-워셜 알고리즘 호출

private:
    int vertices; // 정점의 수
    std::vector<std::vector<int>> dist; // 거리 행렬
};

// 그래프 생성자 정의
Graph::Graph(int vertices) {
    this->vertices = vertices;
    dist.resize(vertices, std::vector<int>(vertices, INF));

    for (int i = 0; i < vertices; ++i) {
        dist[i][i] = 0; // 자기 자신으로의 거리는 0으로 초기화
    }
}

// 간선 추가 함수 정의
void Graph::addEdge(int u, int v, int weight) {
    dist[u][v] = weight; // 가중치를 거리 행렬에 추가
}

// 플로이드-워셜 알고리즘 함수 정의
void Graph::floydWarshall() {
    std::vector<std::vector<int>> distCopy = dist; // 거리 행렬 복사

    for (int k = 0; k < vertices; ++k) {
        for (int i = 0; i < vertices; ++i) {
            for (int j = 0; j < vertices; ++j) {
                // 정점 k를 통해 i에서 j로 가는 경로가 더 짧은 경우 업데이트
                if (distCopy[i][k] != INF && distCopy[k][j] != INF && distCopy[i][k] + distCopy[k][j] < distCopy[i][j]) {
                    distCopy[i][j] = distCopy[i][k] + distCopy[k][j];
                }
            }
        }
    }

    // 최단 거리 행렬 출력
    std::cout << "정점 쌍 간의 최단 거리 행렬:" << std::endl;
    for (int i = 0; i < vertices; ++i) {
        for (int j = 0; j < vertices; ++j) {
            if (distCopy[i][j] == INF) {
                std::cout << "INF ";
            } else {
                std::cout << distCopy[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

// 메인 함수
int main() {
    Graph g(4);
    g.addEdge(0, 1, 5);
    g.addEdge(0, 3, 10);
    g.addEdge(1, 2, 3);
    g.addEdge(2, 3, 1);

    g.floydWarshall();

    return 0;
}

 

설명

1. 그래프 클래스:
   • vertices: 그래프의 정점 수.
   • dist: 정점 간의 거리를 저장하는 거리 행렬. 초기에는 모든 값을 무한대로 설정하고, 자기 자신으로의 거리는 0으로 설정합니다.
2. addEdge 함수:
   • 정점 u에서 정점 v로의 간선과 가중치를 거리 행렬에 추가합니다.
3. floydWarshall 함수:
   • 플로이드-워셜 알고리즘을 수행하여 모든 정점 쌍 간의 최단 거리를 계산합니다.
   • 정점 k를 중간에 거쳐가는 경로를 고려하여 거리 행렬을 업데이트합니다.
   • 최종 최단 거리 행렬을 출력합니다.

플로이드-워셜 알고리즘의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 27: 최소 신장 트리 (크루스칼, 프림 알고리즘)"에 대해 학습하겠습니다.