Prim & Dijkstra

Prim과 Dijkstra는 모두 그리디 알고리즘 중 하나이다.

 

Prim은 최소 스패닝 트리를 구하는데 사용되고,

Dijkstra는 한 노드에서 모든 노드로 최단 경로를 구하는데 사용된다.

두 알고리즘은 상당히 유사한데

 

차이점으로는

Prim은 vertex 집합으로 부터 가까이 있는 노드를 선택하며 vertex 집합을 확장해 나가는 것이고,

Dikstra는 하나의 노드에서 가까이 있는 노드를 선택하며 vertex를 확장한다.

 

둘다 그리디하게 가까이 있는 노드로 퍼져나가며 최소 스패닝 트리를 구하거나, 최단 경로를 구하는 것이다.

 

두 알고리즘 모두 우선순위 큐를 사용하면 더 효율적인 알고리즘을 구성할 수 있는데,

연습삼아 우선순위 큐를 사용하지 않고 코드를 작성해봤다.

 

Prim

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

int W[5][5] = {
        {0, 1, 3, MX, MX},
        {1, 0, 3, 6, MX},
        {3, 3, 0, 4, 2},
        {MX, 6, 4, 0, 5},
        {MX, MX, 2, 5, 0}
};

vector<pair<int, int>> F;

void prim(int n) {
    int i, vnear, min;
    pair<int, int> e;
    int nearest[n + 1], distance[n + 1];

    F.clear();

    for (i = 2; i <= n; i++) {
        nearest[i] = 1;
        distance[i] = W[0][i-1];
    }

    for (int repeat = 1; repeat < n; repeat++) {
        //가장 가까운 vertex 뽑기
        min = MX;
        for (i = 2; i <= n; i++) {
            if (distance[i] >= 0 && distance[i] < min) {
                min = distance[i];
                vnear = i;
            }
        }
        e = {vnear, nearest[vnear]};
        F.push_back(e);
        distance[vnear] = -1;

        // 새로 추가된 vnear노드를 포함한 vertex 집합과 각 vertex 간의 거리 업데이트
        for (i = 2; i <= n; i++) {
            if (W[i-1][vnear-1] < distance[i]) {
                distance[i] = W[i-1][vnear-1];
                nearest[i] = vnear;
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    prim(5);

    for(auto a : F){
        cout << a.first << ' ' << a.second << '\n';
    }

}

 

 

Dijkstra

#include <bits/stdc++.h>

#define MX 1'000'003
using namespace std;

int W[5][5] = {
        {0, 7, 4, 6, 1},
        {MX, 0, MX, MX, MX},
        {MX, 2, 0, 5, MX},
        {MX, 3, MX, 0, MX},
        {MX, MX, MX, 1, 0}
};

vector<pair<int, int>> F;

void dijkstra(int n) {
    int i, vnear, min;
    pair<int, int> e;
    int touch[n + 1], length[n + 1];

    F.clear();

    for (i = 2; i <= n; i++) {
        touch[i] = 1;
        length[i] = W[0][i - 1];
    }

    for (int repeat = 1; repeat < n; repeat++) {
        //vertex 1번과 가장 가까운 vertex 뽑기
        min = MX;
        for (i = 2; i <= n; i++) {
            if (length[i] >= 0 && length[i] < min) {
                min = length[i];
                vnear = i;
            }
        }
        e = {vnear, touch[vnear]};
        F.push_back(e);

        // 새로 추가된 vnear노드를 경유하는 각 vertex 간의 거리 업데이트
        for (i = 2; i <= n; i++) {
            if (length[vnear] + W[vnear-1][i-1] < length[i]) {
                length[i] = length[vnear] + W[vnear-1][i-1];
                touch[i] = vnear;
            }
        }
        length[vnear] = -1;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    dijkstra(5);

    for (auto a: F) {
        cout << a.first << ' ' << a.second << '\n';
    }

}