[C++로 배우는 알고리즘과 자료구조 심화] Day 9: 최단 경로 알고리즘 심화 (벨만-포드, 존슨 알고리즘)

최단 경로 알고리즘

최단 경로 알고리즘은 가중치 그래프에서 주어진 두 정점 간의 최단 경로를 찾는 알고리즘입니다. 대표적인 알고리즘으로는 다익스트라 알고리즘(Dijkstra's Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 그리고 존슨 알고리즘(Johnson's Algorithm)이 있습니다.

오늘은 벨만-포드 알고리즘과 존슨 알고리즘에 대해 심화 학습하겠습니다.

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 최단 경로를 찾을 수 있는 알고리즘입니다. 그러나 음의 사이클이 있는 경우에는 사용할 수 없습니다.

벨만-포드 알고리즘의 시간 복잡도:

• (O(VE)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.

벨만-포드 알고리즘 구현

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

// 간선 구조체 정의
struct Edge {
    int src, dest, weight;
};

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices, int edges);
    void addEdge(int src, int dest, int weight);
    void bellmanFord(int src);

private:
    int V, E;
    std::vector<Edge> edges;
};

// 그래프 생성자 정의
Graph::Graph(int vertices, int edges) {
    this->V = vertices;
    this->E = edges;
}

// 간선 추가 함수 정의
void Graph::addEdge(int src, int dest, int weight) {
    edges.push_back({src, dest, weight});
}

// 벨만-포드 알고리즘 함수 정의
void Graph::bellmanFord(int src) {
    std::vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    // 모든 간선에 대해 최단 거리 계산
    for (int i = 1; i <= V - 1; ++i) {
        for (int j = 0; j < E; ++j) {
            int u = edges[j].src;
            int v = edges[j].dest;
            int weight = edges[j].weight;

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // 음의 사이클 존재 여부 확인
    for (int j = 0; j < E; ++j) {
        int u = edges[j].src;
        int v = edges[j].dest;
        int weight = edges[j].weight;

        if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
            std::cout << "그래프에 음의 사이클이 존재합니다." << std::endl;
            return;
        }
    }

    // 최단 거리 출력
    std::cout << "정점 " << src << "로부터의 최단 거리:" << std::endl;
    for (int i = 0; i < V; ++i) {
        std::cout << "정점 " << i << ": " << dist[i] << std::endl;
    }
}

// 메인 함수
int main() {
    int V = 5; // 정점의 수
    int E = 8; // 간선의 수
    Graph g(V, E);

    g.addEdge(0, 1, -1);
    g.addEdge(0, 2, 4);
    g.addEdge(1, 2, 3);
    g.addEdge(1, 3, 2);
    g.addEdge(1, 4, 2);
    g.addEdge(3, 2, 5);
    g.addEdge(3, 1, 1);
    g.addEdge(4, 3, -3);

    g.bellmanFord(0);

    return 0;
}

 

존슨 알고리즘 (Johnson's Algorithm)

존슨 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘입니다. 이는 벨만-포드 알고리즘과 다익스트라 알고리즘을 결합하여 음의 가중치를 처리할 수 있습니다.

존슨 알고리즘의 시간 복잡도:

• (O(V^2 \log V + VE)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.

존슨 알고리즘 구현

#include <iostream>
#include <vector>
#include <list>
#include <climits>
#include <queue>
#include <utility>

// 그래프 클래스 정의
class Graph {
public:
    Graph(int vertices);
    void addEdge(int u, int v, int weight);
    void johnson();

private:
    int vertices;
    std::vector<std::list<std::pair<int, int>>> adjList;

    void bellmanFord(int src, std::vector<int>& dist);
    void dijkstra(int src, std::vector<int>& dist);
};

// 그래프 생성자 정의
Graph::Graph(int vertices) {
    this->vertices = vertices;
    adjList.resize(vertices);
}

// 간선 추가 함수 정의
void Graph::addEdge(int u, int v, int weight) {
    adjList[u].push_back(std::make_pair(v, weight));
}

// 벨만-포드 알고리즘 함수 정의
void Graph::bellmanFord(int src, std::vector<int>& dist) {
    dist.assign(vertices + 1, INT_MAX);
    dist[src] = 0;

    for (int i = 1; i <= vertices; ++i) {
        for (int u = 0; u < vertices; ++u) {
            for (auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }
}

// 다익스트라 알고리즘 함수 정의
void Graph::dijkstra(int src, std::vector<int>& dist) {
    dist.assign(vertices, INT_MAX);
    dist[src] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push(std::make_pair(0, src));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto& edge : adjList[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(std::make_pair(dist[v], v));
            }
        }
    }
}

// 존슨 알고리즘 함수 정의
void Graph::johnson() {
    std::vector<int> h(vertices + 1);
    Graph g(vertices + 1);

    for (int u = 0; u < vertices; ++u) {
        for (auto& edge : adjList[u]) {
            int v = edge.first;
            int weight = edge.second;
            g.addEdge(u, v, weight);
        }
        g.addEdge(vertices, u, 0);
    }

    g.bellmanFord(vertices, h);

    for (int u = 0; u < vertices; ++u) {
        for (auto& edge : adjList[u]) {
            int v = edge.first;
            edge.second += h[u] - h[v];
        }
    }

    for (int u = 0; u < vertices; ++u) {
        std::vector<int> dist(vertices);
        dijkstra(u, dist);
        for (int v = 0; v < vertices; ++v) {
            if (dist[v] != INT_MAX) {
                dist[v] += h[v] - h[u];
            }
        }

        std::cout << "정점 " << u << "로부터의 최단 거리:" << std::endl;
        for (int v = 0; v < vertices; ++v) {
            std::cout << "정점 " << v << ": " << dist[v] << std::endl;
        }
    }
}

// 메인 함수
int main() {
    Graph g(5);

    g.addEdge(0, 1, 3);
    g.addEdge(0, 2, 8);
    g.addEdge(0, 4, -4);
    g.addEdge(1, 3, 1);
    g.addEdge(1, 4, 7);
    g.addEdge(2, 1, 4);
    g.addEdge(3, 0, 2);
    g.addEdge(3, 2, -5);
    g.addEdge(4, 3, 6);

    g.johnson();

    return 0;
}

 

설명

1. 벨만-포드 알고리즘:
   • 음의 가중치를 허용하며, 음의 사이클이 있는 경우를 감지합니다.
   • 각 간선을 반복적으로 완화하여 최단 거리를 계산합니다.
2. 존슨 알고리즘:
   • 모든 정점 쌍 간의 최단 경로를 찾기 위해 벨만-포드 알고리즘과 다익스트라 알고리즘을 결합합니다.
   • 먼저 그래프에 새로운 정점을 추가하고 벨만-포드 알고리즘을 사용하여 각 정점의 잠정적 거리를 계산합니다.
   • 간선의 가중치를 재계산하여 음의 가중치를 제거한 후, 다익스트라 알고리즘을 사용하여 최단 거리를 계산합니다.

벨만-포드 알고리즘과 존슨 알고리즘의 심화 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 10: 위상 정렬 (Topological Sorting)"에 대해 학습하겠습니다.