Prim vs Dijkstra (프림 다익스트라 비교)

프림 알고리즘 (최소스패닝트리)

• 그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘

 

프림 알고리즘을 적용한 모습

#include <stdio.h>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
 
int visited[10001];
int V, E;
int ans;
 
vector<pair<int, int>> map[10001];
 
void prim(int start)
{
    visited[start] = 1;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for(int i = 0; i < map[start].size(); i++)
    {
        int next = map[start][i].first;
        int nextCost = map[start][i].second;
        
        pq.push(make_pair(nextCost, next));
    }
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(visited[now] == 1)
        {
            continue;
        }
        
        visited[now] = 1;
        
        ans += nowCost;
        
        for(int i = 0; i < map[now].size(); i++)
        {
            int next = map[now][i].first;
            int nextCost = map[now][i].second;
            
            pq.push(make_pair(nextCost, next));
        }
    }
}
 
int main(void)
{
    freopen("B1197_input.txt", "r", stdin);
    
    scanf("%d %d", &V, &E);
    
    for(int i = 0; i < E; i++)
    {
        int from, to, weight;
        scanf("%d %d %d", &from, &to, &weight);
        
// 무향
        map[from].push_back(make_pair(to, weight));
        map[to].push_back({from, weight});
    }
    
    prim(1);
    
    printf("%d", ans);
    
    return 0;
}
 

 

 

 

다익스트라 알고리즘 (최단경로트리)

• 시작 노드(1)로부터 그래프 상에 존재하는 모든 노드, 즉 두 노드 사이의 최단거리를 구하는 알고리즘

 

다익스트라 알고리즘을 적용한 모습

#include <stdio.h>
#include <vector>
#include <queue>
#include <functional> // 우선순위큐의 greater
using namespace std;
 
int d[20001];
int V, E;
int start;
 
vector<pair<int, int>> v[20001];
 
void solve(int start)
{
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(d[now] != nowCost)
        {
            continue;
        }
        
        for(int i = 0; i < (int)v[now].size(); i++)
        {
            int next = v[now][i].first;
            int nextCost = d[now]+v[now][i].second;
            
            if(nextCost < d[next])
            {
                d[next] = nextCost;
                pq.push({nextCost, next});
            }
        }
    }
}
 
int main(void)
{
    freopen("B1753_input.txt", "r", stdin);
    
    scanf("%d %d %d", &V, &E, &start);
    
    for(int i = 1; i <= V; i++)
    {
        d[i] = 9999999;
    }
 
    for(int i = 1; i <= E; i++)
    {
        int from, to, weight;
        scanf("%d %d %d", &from, &to, &weight);    
        
 // 유향
        v[from].push_back({to, weight});
    }
    
    solve(start);
    
    for(int i = 1; i <= V; i++)
    {
        if(d[i] == 9999999)
        {
            printf("INF\n");
        }
        else
        {
            printf("%d\n", d[i]);    
        }
    }
    
    return 0;
}
 

 

차이점

1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다.

   ※ 프림은 1->3의 비용이 3인 반면에, 다익스트라는 1->3의 비용이 2이다.

2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다.

3. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다.

   -> 최소스패닝트리가 최단경로트리를, 최단경로트리가 최소스패닝트리를 보장하지 않는다.