728x90
import heapq
def dijkstra(u):
# 시작 셋팅
D[u] = 0
q = []
heapq.heappush(q, (D[u],u))
# 정점 갯수 만큼 반복
for i in range(V):
# 가중치 최솟값 찾기
min_v = 987654321
now, u = heapq.heappop(q)
# 방문 처리
visit[u] = 1
# 인접한 정점 업데이터
for v in range(V):
if adj[u][v] != 0 and visit[v] == 0 and D[v] > D[u] + adj[u][v]:
D[v] = D[u] + adj[u][v]
heapq.heappush(q, (D[v],v))
###############################################################################
V, E = map(int,input().split())
# 인접 행렬
adj = [[0] * V for _ in range(V)]
# 가중치
D = [987654321] * V
# 방문 여부
visit = [0] * V
# 입력
for i in range(E):
s, e, w = map(int,input().split())
adj[s][e] = w
adj[e][s] = w
dijkstra(0)
print(D)
최소값 구하는 방법을 우선순위큐로 사용하였다.
'알고리즘 이론' 카테고리의 다른 글
조합 (0) | 2021.10.25 |
---|---|
그래프 - 최단 경로 (0) | 2021.10.13 |
그래프 - MST(최소 비용 신장 트리) (0) | 2021.10.13 |
순열 (0) | 2021.10.06 |