다익스트라 알고리즘 구현

구현 방법

• 출발 노드 설정
• 최단 거리 테이블 초기화
• 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
• 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
• 3, 4 번 과정 반복

-> 그리디 알고리즘 + 다이나믹 프로그래밍

 

코드 (우선순위큐 사용X)

import sys
input = sys.stdin.readline
# 노드, 간선
n, m = map(int,input().split())
# 시작노드
start = int(input())
INF = int(1e9)
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
distance = [INF] * (n + 1)
# 모든 간선 입력
for _ in range(m):
    a, b, c = map(int,input().split())
    graph[a].append((b, c)) # a,b의 거리 c

# 방문되지 않은 거리 중 최소 거리 반환
def get_smallest_index():
    min_value = INF
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

# 다익스트라 수행
def dijkstra(start):
    # 시작노드 초기화
    distance[start] = 0
    visited[start] = True
    # 거리업데이트
    for j in graph[start]:
        distance[j[0]] = j[1]

    for i in range(1, n - 1):
        # 최소 거리값 인덱스
        now = get_smallest_index()
        visited[now] = True
        # 최소 거리와 연결된 그래프들의 거리
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재거리를 거치는 거리가 더 최소 거리라면 갱신
            if cost < distance[j[0]]:
                distance[j[0]] = cost

# 다익스트라알고리즘 실행
dijkstra(start)

# 모든 거리 출력
for i in range(1, n + 1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

코드 (우선순위 큐 사용O)

import heapq
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
start = int(input())
graph = [[] for _ in range(n + 1)]
INF = int(1e9)
distance = [INF] * (n + 1)
# 모든 간선 입력
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b, c))

def dijkstra(start):
    # 우선순위 큐 생성
    q = []
    # 힙에 출발노드 정보 넣기(거리, 노드)
    heapq.heappush(q, (0, start))
    # 출발거리 0으로 업데이트
    distance[start] = 0
    while q:
        # 힙에 있는 거리, 노드 값 pop
        dist, now = heapq.heappop(q)
        # 꺼낸 거리가 저장된 거리 값보다 큰 경우 무시
        if distance[now] < dist:
            continue
        # 연결되어있는 모든 노드 탐색
        for i in graph[now]:
            # 현재있는 곳을 거쳐가는 경우가 더 최단경로라면 값 업데이트
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                # 힙에 거리, 노드 정보 삽입
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 수행
dijkstra(start)
# 모든 값 출력
for i in range(1, n + 1):
    if distance[i] == INF:
        print('INFINITY')
    else:
        print(distance[i])