다익스트라 알고리즘(Dijkstra algorithm)

 

start: 1 end: 4로 가정

출발 노드로부터 각 노드에 도작하기까지 걸리는 최단 경로를 구하자

일반적으로 distance 값은 10억 미만으로 주어진다. 

방문하지 않은 노드 중에 가장 짧은 거리인 노드를 구하는 경우, 가장 짧은 거리가 중복으로 여러 개 일 수도 있다. 이때 통상적으로 노드 번호가 작은 경우를 가장 짧은 노드로 선택한다. 

 

1. 구현된 코드와 동일한 폴더 안에 a.txt로 저장한다. 

6 10
1
1 2 2
1 6 3
2 4 4
2 3 1
3 4 2
4 1 4
4 5 1
5 6 1
6 2 5
6 5 1

2. 코드 구현 

n,m = map(int, input().split())
start = int(sys.stdin.readline())
INF = 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))

# 아직 방문하지 않고 거리가 가장 짧은 노드 구하기  
def get_smallest_node():
    min_val = INF
    idx = 0
    for i in range(1, n+1):
        if distance[i] < min_val and not visited[i]:
            min_val = distance[i]
            idx = i
    return idx

def dijkstra(start):
    # 목적지 노드가 자기 자신(출발 노드)인 경우 거리는 0
    distance[start]=0
    # 자기 자신 방문 처리
    visited[start]=True
    for j in graph[start]:
        distance[j[0]]=j[1]
    # 출발지 노드를 제외한 n-1개의 노드에 대해 반복
    for i in range(n-1):
        now = get_smallest_node()
        # 방문 처리
        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('infinite')
    # 도달 가능한 경우 최단 경로 출력 
    else:
        print(distance[i])

 

3. heapq를 사용한 코드

import heapq

n,m = map(int, input().split())
start = int(input())
INF = 1e9
graph = [[] for _ in range(n+1)]
distance = [INF]*(n+1)

for i in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

def dijkstra(start):
    distance[start] = 0
    h = []
    heapq.heappush(h,(0, start))
    while h:
        dist, now = heapq.heappop(h)
        # 현재 노드가 이미 처리된적 있다면 넘어감 
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = distance[now] + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(h,(cost,i[0]))

dijkstra(start)

for i in range(n+1):
    if distance[i] == 'INF':
        print('INFINITE')
    else:
        print(distance[i])