최단 경로 알고리즘(다익스트라)

출발지에서 모든 노드로 가는 최단 거리(비용)을 구하는 알고리즘이다.

알고리즘은 다음과 같이 구현한다.

1. 모든 노드에 대해 비용이 무한인 배열 a를 선언한다.

2. a에 출발 노드는 0으로 세팅.

3. 모든 노드에 대해 방문 체크할 수 있는 배열 b를 선언한다.

4. b에 출발 노드 방문으로 체크

5. 출발노드와 연결된 노드를 탐색하면서 탐색노드로 가능 비용을  a에 업데이트 한다.

6. 방문하지 않는 노드 중 최소 비용 노드를 선택하고 연결된 노드를 탐색하면서 비용이 기존 a보다 작으면 a에 업데이트 한다.

7. 모든 노드를 방문할 때까지 6을 반복한다.

 

이를 구현한 코드는 아래와 같다.

# 최단 경로를 선형으로 찾는 방법
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드, 간선 개수 
n, m = map(int, input().split())
# 시작 노드 번호
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
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())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b,c))

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node() -> int:
    smallest_node = 0
    smallest_value = INF
    for i in range(1, n+1):
        if visited[i] == False:
            if smallest_value >  distance[i]:
                smallest_value = distance[i]
                smallest_node = i
    return smallest_node

def dijkstra(_start : int) -> None:
    # 시작 노드에 대해서 초기화
    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 distance[j[0]] > cost:
                distance[j[0]] = cost
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달 할 수 없는 경우 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])


# 최단 경로를 log(N)으로 찾는 방법

import heapq
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for _ in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
# 모든 간선 정보 입력
for _ in range(n):
    a,b,c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c
    graph[a].append((b,c))

def dijkstraPriorityQueue(_start : int) -> None:
    q = []
    # 시작 노드로 가기 위한 최단 거리는 0으로 설정, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        # 가장 최단 거리가 짧은 노드 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = i[1] + dist
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstraPriorityQueue(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달 할 수 없는 경우 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

방문하지 않은 노드 중 비용이 가장 적은 노드를 선택할 때 최소 힙을 사용한 우선순위 큐를 이용하면 시간 복잡도를 줄일 수 있다.

 

참조 : (이코테 2021 강의 몰아보기) 7. 최단 경로 알고리즘 - YouTube