[c++] 최단 경로 알고리즘

08 Dec 2023

이번 포스트에서는 C++를 사용하여 그래프 내의 최단 경로를 찾는 알고리즘에 대해 알아보겠습니다.

Dijkstra 알고리즘

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 최단 경로를 찾는 데 사용됩니다.

예제 코드:

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

using namespace std;

#define INF INT_MAX

void dijkstra(vector<vector<pair<int, int>>> &adj, vector<int> &dist, int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, start));
    dist[start] = 0;

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

        for (auto &neighbor : adj[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int n = 5; // 그래프의 노드 수
    vector<vector<pair<int, int>>> adjList(n);
    vector<int> dist(n, INF);

    // 그래프의 간선 정보 추가
    adjList[0].push_back(make_pair(1, 5));
    adjList[0].push_back(make_pair(2, 3));
    adjList[1].push_back(make_pair(3, 6));
    adjList[1].push_back(make_pair(2, 2));
    adjList[2].push_back(make_pair(4, 4));
    adjList[2].push_back(make_pair(3, 7));
    adjList[3].push_back(make_pair(4, 1));
    
    dijkstra(adjList, dist, 0);

    // 결과 출력
    for (int i = 0; i < n; i++) {
        cout << "0에서 " << i << "까지의 최단 거리: " << dist[i] << endl;
    }

    return 0;
}

Bellman-Ford 알고리즘

벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서도 최단 경로를 찾는 데 사용됩니다.

예제 코드:

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

using namespace std;

#define INF INT_MAX

struct Edge {
    int source, dest, weight;
};

void bellmanFord(vector<Edge> &edges, int n, int start) {
    vector<int> dist(n, INF);
    dist[start] = 0;

    for (int i = 1; i < n; i++) {
        for (const auto &edge : edges) {
            int u = edge.source;
            int v = edge.dest;
            int weight = edge.weight;

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

    // 음수 사이클 검사
    for (const auto &edge : edges) {
        int u = edge.source;
        int v = edge.dest;
        int weight = edge.weight;

        if (dist[u] != INF && dist[u] + weight < dist[v]) {
            cout << "음수 사이클이 존재합니다." << endl;
            return;
        }
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        cout << start << "에서 " << i << "까지의 최단 거리: " << dist[i] << endl;
    }
}

int main() {
    int n = 5; // 그래프의 노드 수
    vector<Edge> edges = {{0, 1, 5}, {0, 2, 3}, {1, 3, 6}, {1, 2, 2}, {2, 4, 4}, {2, 3, 7}, {3, 4, 1}};
    
    bellmanFord(edges, n, 0);

    return 0;
}

목차

Dijkstra 알고리즘

예제 코드:

Bellman-Ford 알고리즘

예제 코드:

참고 자료