알고리즘 이론

그래프 - 최단 경로(다익스트라 - 우선순위 큐)

HTG 2021. 12. 14. 19:52
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