[알고리즘] 다익스트라, 프림, 크루스칼

1. input.txt로부터 정점 수, 간선 수, 시작 정점 입력 받기
2. 간선 입력 (u, v, w)
3. 최단 거리 출력
4. 최단 경로(경로 역추적 포함) 출력
5. 파일 없거나 경로 없을 때 오류 처리

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <limits>
#include <stack>
using namespace std;

// 무한대 정의
const int INF = numeric_limits<int>::max();

////////////////////////////////////////////////////////
// 다익스트라 함수: 최소 거리 및 경로 계산
////////////////////////////////////////////////////////
void dijkstra(int N, int start, const vector<vector<pair<int, int>>>& adj,
              vector<int>& dist, vector<int>& parent) {
    dist.assign(N, INF);      // 모든 정점까지의 거리 초기화
    parent.assign(N, -1);     // 경로 추적용 부모 정보 초기화
    dist[start] = 0;

    // 우선순위 큐: {거리, 정점}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > dist[u]) continue; // 이미 처리된 더 짧은 거리 존재 시 무시

        for (auto [v, weight] : adj[u]) {
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                parent[v] = u; // 경로 추적용
                pq.push({dist[v], v});
            }
        }
    }
}

////////////////////////////////////////////////////////
// 경로 출력 함수: parent[] 배열 이용해 역추적
////////////////////////////////////////////////////////
void printPath(int v, const vector<int>& parent) {
    stack<int> path;
    int cur = v;
    while (cur != -1) {
        path.push(cur);
        cur = parent[cur];
    }

    while (!path.empty()) {
        cout << path.top();
        path.pop();
        if (!path.empty()) cout << " → ";
    }
}

////////////////////////////////////////////////////////
// 메인 함수
////////////////////////////////////////////////////////
int main() {
    ifstream fin("input.txt");
    if (!fin) {
        cerr << "❌ input.txt 파일 열기 실패\n";
        return 1;
    }

    int N, M, start;
    fin >> N >> M >> start;

    // 인접 리스트: adj[u] = {{v1, w1}, {v2, w2}, ...}
    vector<vector<pair<int, int>>> adj(N);

    // 간선 정보 입력
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].emplace_back(v, w); // u → v 가중치 w
    }

    vector<int> dist, parent;

    // 다익스트라 실행
    dijkstra(N, start, adj, dist, parent);

    // 최단 거리 출력
    cout << "📌 [최단 거리 결과] 시작 정점: " << start << "\n";
    for (int i = 0; i < N; ++i) {
        if (dist[i] == INF)
            cout << "정점 " << i << ": 도달 불가\n";
        else
            cout << "정점 " << i << ": 거리 = " << dist[i] << "\n";
    }

    cout << "\n📌 [최단 경로 출력]\n";
    for (int i = 0; i < N; ++i) {
        if (i == start) continue;

        cout << "→ " << start << " → " << i << " 경로: ";
        if (dist[i] == INF) {
            cout << "도달 불가\n";
        } else {
            printPath(i, parent);
            cout << " (총 거리: " << dist[i] << ")\n";
        }
    }

    return 0;
}

 

 

다익스트라, 벨만-포드, 플로이드-워셜

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <limits>
#include <stack>
using namespace std;

const int INF = numeric_limits<int>::max();

// 다익스트라: 음수 가중치 없음
void dijkstra(int N, int start, const vector<vector<pair<int, int>>>& adj,
              vector<int>& dist, vector<int>& parent) {
    dist.assign(N, INF);
    parent.assign(N, -1);
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

// 벨만-포드: 음수 가중치 허용, 음수 사이클 검사 가능
bool bellmanFord(int N, int start, const vector<tuple<int, int, int>>& edges,
                 vector<int>& dist, vector<int>& parent) {
    dist.assign(N, INF);
    parent.assign(N, -1);
    dist[start] = 0;

    for (int i = 0; i < N - 1; ++i) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                parent[v] = u;
            }
        }
    }

    // 음수 사이클 검사
    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[v] > dist[u] + w)
            return false; // 음수 사이클 존재
    }

    return true;
}

// 플로이드-워셜: 전체 쌍 최단 경로
void floydWarshall(int N, const vector<vector<pair<int, int>>>& adj) {
    vector<vector<int>> dist(N, vector<int>(N, INF));
    for (int i = 0; i < N; ++i) dist[i][i] = 0;

    for (int u = 0; u < N; ++u)
        for (auto [v, w] : adj[u])
            dist[u][v] = min(dist[u][v], w);

    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    cout << "\n📌 [플로이드-워셜 전체 최단 거리]\n";
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (dist[i][j] == INF) cout << "INF ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
}

// 경로 출력
void printPath(int v, const vector<int>& parent) {
    if (v == -1) return;
    printPath(parent[v], parent);
    cout << v << " ";
}

int main() {
    ifstream fin("input.txt");
    if (!fin) {
        cerr << "❌ input.txt 파일 열기 실패\n";
        return 1;
    }

    int N, M, start;
    string graphType;
    fin >> N >> M >> start >> graphType;

    vector<vector<pair<int, int>>> adj(N);
    vector<tuple<int, int, int>> edges;

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        edges.emplace_back(u, v, w);
        if (graphType == "undirected") {
            adj[v].emplace_back(u, w);
            edges.emplace_back(v, u, w);
        }
    }

    cout << "========== 🚀 시작 정점: " << start << " ==========\n";

    // ✅ 다익스트라
    vector<int> dist_d, parent_d;
    dijkstra(N, start, adj, dist_d, parent_d);
    cout << "\n📌 [다익스트라 최단 거리]\n";
    for (int i = 0; i < N; ++i)
        cout << "정점 " << i << ": " << (dist_d[i] == INF ? -1 : dist_d[i]) << "\n";

    cout << "\n📌 [다익스트라 경로]\n";
    for (int i = 0; i < N; ++i) {
        if (i == start || dist_d[i] == INF) continue;
        cout << start << " → " << i << ": ";
        printPath(i, parent_d);
        cout << "(거리: " << dist_d[i] << ")\n";
    }

    // ✅ 벨만-포드
    vector<int> dist_bf, parent_bf;
    if (bellmanFord(N, start, edges, dist_bf, parent_bf)) {
        cout << "\n📌 [벨만-포드 최단 거리]\n";
        for (int i = 0; i < N; ++i)

 

다 넣은 수정본

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>
#include <tuple>
#include <algorithm>
#include <limits>
#include <set>
#include <numeric>
using namespace std;

const int INF = numeric_limits<int>::max();

//////////////////////////////////////////////////////////////
// [1] 그래프 데이터 및 입력 함수
//////////////////////////////////////////////////////////////

int N, M, start;
string graphType; // "directed" or "undirected"
vector<vector<pair<int, int>>> adj; // 인접 리스트
vector<tuple<int, int, int>> edges; // 간선 리스트 (u, v, w)

void loadGraph(const string& filename) {
    ifstream fin(filename);
    if (!fin) {
        cerr << "❌ 파일 열기 실패\n";
        exit(1);
    }

    fin >> N >> M >> start >> graphType;
    adj.assign(N, {});
    edges.clear();

    for (int i = 0; i < M; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        edges.emplace_back(u, v, w);
        if (graphType == "undirected") {
            adj[v].emplace_back(u, w);
            edges.emplace_back(v, u, w);
        }
    }
    fin.close();
}

//////////////////////////////////////////////////////////////
// [2] 다익스트라 알고리즘 (양수 가중치 전용)
//////////////////////////////////////////////////////////////

void dijkstra(int s, vector<int>& dist, vector<int>& parent) {
    dist.assign(N, INF);
    parent.assign(N, -1);
    dist[s] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

//////////////////////////////////////////////////////////////
// [3] 벨만-포드 알고리즘 (음수 가중치 허용)
//////////////////////////////////////////////////////////////

bool bellmanFord(int s, vector<int>& dist, vector<int>& parent) {
    dist.assign(N, INF);
    parent.assign(N, -1);
    dist[s] = 0;

    for (int i = 0; i < N - 1; ++i) {
        for (auto [u, v, w] : edges) {
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                parent[v] = u;
            }
        }
    }

    for (auto [u, v, w] : edges) {
        if (dist[u] != INF && dist[v] > dist[u] + w)
            return false; // 음수 사이클 존재
    }
    return true;
}

//////////////////////////////////////////////////////////////
// [4] 플로이드-워셜 알고리즘 (모든 쌍 최단 경로)
//////////////////////////////////////////////////////////////

void floydWarshall() {
    vector<vector<int>> dist(N, vector<int>(N, INF));
    for (int i = 0; i < N; ++i) dist[i][i] = 0;
    for (int u = 0; u < N; ++u)
        for (auto [v, w] : adj[u])
            dist[u][v] = min(dist[u][v], w);

    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                if (dist[i][k] != INF && dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    cout << "\n📌 [플로이드-워셜 전체 최단 거리]" << endl;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j)
            cout << (dist[i][j] == INF ? -1 : dist[i][j]) << " ";
        cout << endl;
    }
}

//////////////////////////////////////////////////////////////
// [5] MST: Prim 알고리즘
//////////////////////////////////////////////////////////////

int primMST() {
    vector<int> key(N, INF);
    vector<bool> inMST(N, false);
    key[0] = 0;
    int total = 0;

    for (int count = 0; count < N; ++count) {
        int u = -1;
        for (int i = 0; i < N; ++i)
            if (!inMST[i] && (u == -1 || key[i] < key[u])) u = i;

        inMST[u] = true;
        total += key[u];

        for (auto [v, w] : adj[u])
            if (!inMST[v] && key[v] > w) key[v] = w;
    }
    return total;
}

//////////////////////////////////////////////////////////////
// [6] MST: Kruskal 알고리즘
//////////////////////////////////////////////////////////////

int find(vector<int>& parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

bool unite(vector<int>& parent, int a, int b) {
    int ra = find(parent, a), rb = find(parent, b);
    if (ra == rb) return false;
    parent[rb] = ra;
    return true;
}

int kruskalMST() {
    vector<int> parent(N);
    iota(parent.begin(), parent.end(), 0);
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) {
        return get<2>(a) < get<2>(b);
    });

    int total = 0;
    for (auto [u, v, w] : edges) {
        if (unite(parent, u, v)) total += w;
    }
    return total;
}

//////////////////////////////////////////////////////////////
// [7] 경로 출력 및 최대/최소 거리 탐색
//////////////////////////////////////////////////////////////

void printPath(int v, const vector<int>& parent) {
    if (v == -1) return;
    printPath(parent[v], parent);
    cout << v << " ";
}

void findExtremes(const vector<int>& dist) {
    int minV = -1, maxV = -1;
    for (int i = 0; i < N; ++i) {
        if (i == start || dist[i] == INF) continue;
        if (minV == -1 || dist[i] < dist[minV]) minV = i;
        if (maxV == -1 || dist[i] > dist[maxV]) maxV = i;
    }
    cout << "\n🔎 최단 경로 도착점: " << minV << " (거리: " << dist[minV] << ")\n";
    cout << "🔎 최장 경로 도착점: " << maxV << " (거리: " << dist[maxV] << ")\n";
}

//////////////////////////////////////////////////////////////
// [8] 동적 그래프 수정 함수
//////////////////////////////////////////////////////////////

void addEdge(int u, int v, int w) {
    adj[u].emplace_back(v, w);
    edges.emplace_back(u, v, w);
    if (graphType == "undirected") {
        adj[v].emplace_back(u, w);
        edges.emplace_back(v, u, w);
    }
    cout << "간선 추가 완료: " << u << " ↔ " << v << " (" << w << ")\n";
}

void removeEdge(int u, int v) {
    adj[u].erase(remove_if(adj[u].begin(), adj[u].end(),
        [&](pair<int, int> p) { return p.first == v; }), adj[u].end());
    edges.erase(remove_if(edges.begin(), edges.end(),
        [&](tuple<int, int, int> t) { return get<0>(t) == u && get<1>(t) == v; }), edges.end());
    if (graphType == "undirected") {
        adj[v].erase(remove_if(adj[v].begin(), adj[v].end(),
            [&](pair<int, int> p) { return p.first == u; }), adj[v].end());
        edges.erase(remove_if(edges.begin(), edges.end(),
            [&](tuple<int, int, int> t) { return get<0>(t) == v && get<1>(t) == u; }), edges.end());
    }
    cout << "간선 제거 완료: " << u << " ↔ " << v << "\n";
}

//////////////////////////////////////////////////////////////
// [9] 메인 함수 - 전체 실행
//////////////////////////////////////////////////////////////

int main() {
    loadGraph("input.txt");
    vector<int> dist, parent;

    cout << "\n📌 [다익스트라 결과]\n";
    dijkstra(start, dist, parent);
    for (int i = 0; i < N; ++i)
        cout << "정점 " << i << ": " << (dist[i] == INF ? -1 : dist[i]) << "\n";
    findExtremes(dist);

    cout << "\n📌 [벨만-포드 결과]\n";
    if (bellmanFord(start, dist, parent)) {
        for (int i = 0; i < N; ++i)
            cout << "정점 " << i << ": " << (dist[i] == INF ? -1 : dist[i]) << "\n";
    } else {
        cout << "음수 사이클 존재\n";
    }

    floydWarshall();

    cout << "\n📌 [MST 결과]\n";
    cout << "Prim MST: 총 가중치 = " << primMST() << "\n";
    cout << "Kruskal MST: 총 가중치 = " << kruskalMST() << "\n";

    // 예시: 동적 그래프 수정
    addEdge(0, N - 1, 7);
    removeEdge(1, 3);

    return 0;
}