[알고리즘] 다익스트라 vs 크루스칼/프림 차이를 알아보자

다익스트라(dijkstra) vs 크루스칼(kruskal) + 프림(prim)

앞선 포스팅에서 다익스트라와 크루스칼/프림 알고리즘에 대하여 설명했다. 

다익스트라는 최단 경로의 해를 구하는 목적이고, 크루스칼과 프림은 MST(최소 신장 트리) 문제를 해결하는 목적이다.

비슷한 그래프 알고리즘 개념이라 혼동이 올 수 있어 세가지 알고리즘을 비교해 본다. 

	다익스트라	크루스칼/프림
용도	최단 경로 탐색	최소 신장 트리 해결
상세 설명	하나의 정점에서 다른 정점(들) 까지의 최단 경로를 탐색	모든 노드를 최소한의 비용으로 방문하는 간선을 탐색
특징	두 정점 간 최단 경로(최소 가중치 간선)만 선택	두 정점 간 최단 경로(간선)가 아니더라도 선택 가능 ( 두 정점 간의 최단 경로를 보장하지 않음 )
구현 방법	heap + DP( 동적 계획법 )	heap + union/find or DP(동적 계획법)
시간복잡도	O(ElogV)	O(ElogE) / O(ElogV)
대표 문제	https://www.acmicpc.net/workbook/view/1711	https://www.acmicpc.net/workbook/view/956

 

앞선 포스팅에 소개한 알고리즘 코드이다. 상세한 설명은 각 포스팅 참조. 

다익스트라( dijkstra )

from heapq import heappush,heappop
def dijkstra(graph,start):
    q = list() ## heapq 생성을 위한 초기 list 
    distance = dict() ## dist 저장을위한 dict 

    distance[start] = 0 ## 시작 노드의 거리는 0
    heappush(q, (0, start)) ## 거리,노드 순으로 q에 넣어서 오름차순 정렬할 것.

    while q:
        dis, node = heappop(q) ## heapq의 값중 거리가 가장 작는 값 꺼내기

        ## 방문할 노드까지의 직접 거리가 현재 확보된 경유거리보다 크면 다음 loop로
        if node in distance and (distance[node] < dis):
            continue

        ## 다음 노드 까지의 거리가 없거나 현재 업데이트된 거리보다 작으면 업데이트
        for key, value in graph[node]:
            cost = distance[node] + value
            if (key not in distance) or ((key in distance) and (cost < distance[key])):
                distance[key] = cost
                heappush(q, (cost, key))
    return distance

graph = {
1 : [(4,15),(5,35)],
2 : [(3,30)],
3 : [(2,40),(5,20)],
4 : [(1,25),(5,10)],
5 : [(3,5),(4,30),(2,50)],
}
distance = dijkstra(graph, 5)
print(distance.values())
print(sum(distance.values()))

 

 

크루스칼( kruskal )

def find(x):## 최상위 부모노드 찾기
    if parent[x] != x : ## 부모노드와 자기자신의 값이 다르면
        parent[x] = find(parent[x]) ## 최상위 부모노드를 찾을때까지 재귀호출
    return parent[x] ## 결국 최상위 부모노드 뽑힘

def union(x,y): ## 노드 합치기 
    x = find(x) ## x의 부모 노드 구하기
    y = find(y) ## y의 부모 노드 구하기
    
    ## x,y의 부모노드 중 큰 값이 작은 값의 부모가 된다
    if x < y : 
        parent[y] = x
    else :
        parent[x] = y

def kruskal():
    global result,distance
    graph.sort()  ##list를 간선의 가중치 기준으로 오름차순 정렬
    for dist,u,v in graph : ## 가중치 가장 낮은 간선부터 loop
        if find(u) != find(v): ## 두 노드의 부모가 다르면
            union(u,v) ## 두 노드를 연결한다 ( 간선 선택 )
            distance += dist ## 가중치 더하기
            result.append((dist,u,v)) ## 결과값에 저장
            print(f'{u} ↔ {v} : {dist}') 

graph = [(3,'a','b'),(1,'a','e'),
         (5,'b','c'),(4,'b','e'),
         (2,'c','d'),(6,'c','e'),
         (7,'d','e')]
## 순환 검사를 위한 dictionary 구현
parent = dict()
for x in ['a','b','c','d','e']:
    parent[x]=x ## 자기 자신을 부모로 갖는 dict 
result = [] ## 결과 저장 list
distance = 0 ## 간선 합 저장
kruskal()
print(result)
print(distance)

 

 

프림( prim )

from collections import defaultdict
from heapq import heapify,heappop,heappush

def prim(start_node):
    global result
    print(f'start : {start_node}')
    q = graph_dict[start_node]
    heapify( q ) ## 시작노드 q에 넣기
    visited.append(start_node) # 시작 노드 방문 처리
    while q:
        dist,start,end = heappop(q) # heapq 활용 dist 낮은 순으로 뽑기
        if end not in visited: # 가중치 낮은 간선의 노드가 방문 전이면
            visited.append(end)
            result.append((dist,start,end))
            print(f'{start} → {end} : {dist}')
            for nd,ns,ne in graph_dict[end]: # 방문한 노드의 다음 노드 탐색
                if ne not in visited:
                    heappush(q,(nd,ns,ne))

graph = [(1,'A','B'),(3,'A','D'),
         (3,'B','C'),(2,'B','D'),(6,'B','E'),(5,'B','F'),
         (4,'C','E'),(4,'C','F'),
         (3,'D','E'),
         (2,'E','F')]
graph_dict = defaultdict(list)
# dictionary로 양방향 그래프 구현
for distance,start,end in graph:
    graph_dict[start].append((distance,start,end))
    graph_dict[end].append((distance,end,start))
visited = [] ## 방문 관리 list
result = [] ## 결과 저장 list
prim('B') ## 'B' 노드부터 시작
print(result)