선택한 정점과 인접하는 정점들 중(BFS + 최소 비용)의 최소 비용 간선이 존재하는 정점을 선택한다.
모든 정점이 선택될 때까지 1, 2번 과정을 반복한다.
from heapq import heappush, heappop
def prim(start):
heap = list()
MST = [0] * (V) # visited라고 생각하면 됨
# 최소 비용 합계
sum_weight = 0
# 힙에서 관리해야 할 데이터
# 가중치, 정점 정보
# 정점 번호를 기준으로 정렬되기 때문에 이렇게 하면 안됨
# heappush(heap, (start, 0))
heappush(heap, (0, start)) # 시작점은 가중치가 0임
while heap:
weight, v = heappop(heap)
# 이미 방문한 지점이면 통과
if MST[v]:
continue
# 방문 처리
MST[v] = 1
# 누적합 추가
sum_weight += weight
# 갈수 있는 노드를 보면서
for next in range(V):
# 갈 수 없는 지점이면 continue
if graph[v][next] == 0:
continue
# 이미 방문한 지점이면 continue
if MST[next]:
continue
heappush(heap, (graph[v][next], next))
return sum_weight
# V는 정점의 개수, E는 간선의 개수
V, E = map(int, input().split())
# 현재는 인접 행렬로 구현되어 있는데, 이것을 인접 리스트로 변경하는 것을 과제로 내주심
graph = [[0] * (V) for _ in range(V)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u][v] = w
graph[v][u] = w # 가중치가 있는 무방향 그래프
result = prim(0)
print(f'최소 비용 = {result}') # 최소 비용 = 175
'''
# 입력
7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
'''
✅ 예제
아래 그래프에 Prim 알고리즘을 적용시켜 보자.
0번 노드에서 출발하여 가장 낮은 가중치인 2번 노드로 나아가게 된다. (0 → 2)
2번 노드에서 가장 낮은 가중치인 1번 노드로 나아간다.(2 → 1)
하지만 1번 노드 이후로 연결되는 다음 노드가 없으므로 가중치가 두 번째로 낮은 6번 노드로 나아간다. (2 → 6)
6번 노드도 역시 다음으로 연결되는 노드가 없으므로 가중치가 마지막으로 낮은 4번 노드로 나아간다.( 2 → 4)
# V: 마지막 정점. 따라서 정점의 개수는 (V+1)개이다.
# E: 간선의 개수
V, E = map(int, input().split())
edge = []
# 간선 집합 생성
for _ in range(E):
u, v, w = map(int, input().split())
edge.append([u, v, w])
edge.sort(key=lambda x : x[2]) # 가중치 기준 오름차순 정렬
parents = [i for i in range(V)] # 대표원소 배열
def find_set(x):
if parents[x] == x:
return x
parents[x] = find_set(parents[x])
return parents[x]
def union(x, y):
x = find_set(x)
y = find_set(y)
if x == y:
return
# 더 작은 루트노트에 합침
if x < y:
parents[y] = x
else:
parents[x] = y
# MST의 간선수 N = 정점 수 - 1
cnt = 0 # 선택한 edge의 수
total = 0 # MST 가중치의 합
for u, v, w in edge:
# 다른 집합이라면
if find_set(u) != find_set(v):
cnt += 1
union(u, v)
total += w
if cnt == V: # MST 구성이 끝나면
break
print(f'최소 비용 = {total}') # 최소 비용 = 175
'''
# 입력
7 11
0 1 32
0 2 31
0 5 60
0 6 51
1 2 21
2 4 46
2 6 25
3 4 34
3 5 18
4 5 40
4 6 51
'''
간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중, 간선의 가중치 합이 최소인 경로를 찾는 알고리즘
시작 정점(s)에서 거리가 최소인 정점(x)을 선택해 나가면서 최단 경로를 도출한다.
시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재할 때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다.
탐욕 기법을 이용한 알고리즘으로, MST의 Prim 알고리즘과 유사하다.
📌 최단 경로 알고리즘
✔ 하나의 시작 정점에서 끝 정점까지의 최단 경로 - Dijkstra 알고리즘: 음의 가중치를 허용하지 않음 - Bellman - Ford 알고리즘: 음의 가중치를 허용함
✔ 모든 정점들에 대한 최단 경로 - Floyd - Warshall (플로이드 - 워샬) 알고리즘
D: 누적 가중치 리스트 / U: 누적 가중치 기반 최종 경로
import heapq
INF = int(1e9) # 무한을 의미하는 값으로 1억
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호 (문제에 따라 다름)
start = 0
# 인접리스트 만들기
graph = [[] for i in range(n)]
# 누적거리를 저장할 테이블 - INF 로 저장
distance = [INF] * n
# 간선 정보를 입력
for _ in range(m):
a, b, w = map(int, input().split())
graph[a].append([b, w]) # 단방향 그래프이다!
def dijkstra(start):
pq = []
# heapq 에 리스트로 저장할 때는 맨 앞의 데이터를 기준으로 정렬된다.
heapq.heappush(pq, (0, start))
distance[start] = 0 # 시작 노드 최단 거리는 0
# 우선순위 큐가 빌 때 까지 반복
while pq:
# 가장 최단 거리인 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(pq)
# 현재 노드가 이미 처리됐다면 skip
# 예제 그림: c 위치 가중치 3, 4 로 도착가능 [참고]
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드 확인
for next in graph[now]:
next_node = next[0]
cost = next[1] # 다음 노드의 가중치
new_cost = dist + cost # 누적값(현재까지의 누적값 + 다음 노드 가중치)
# 다음 노드를 가는 데 더 많은 비용이 드는 경우
if new_cost >= distance[next_node]:
continue
distance[next_node] = new_cost # next_node 까지 가는데 비용은 new_cost
heapq.heappush(pq, (new_cost, next_node))
# 다익스트라 알고리즘 실행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리 출력
for i in range(n):
# 도달할 수 없는 경우, 무한 출력
if distance[i] == INF:
print("INF", end=' ')
else:
print(distance[i], end=' ')
# 출력: 0 2 3 9 6 10
# -> 0번 노드에서 갈 수 있는 다른 노드들까지의 최단거리들을 모두 구할 수 있다.
# - 다익스트라 한 번이면, 하나의 정점 -> 다른 정점들까지의 최단거리들을 모두 구한다.
'''
# 입력
6 8
0 1 2
0 2 4
1 2 1
1 3 7
2 4 3
3 4 2
3 5 1
4 5 5
'''
