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

반응형

최단 경로 알고리즘이란 단어 그대로 여러 개의 경로중에서 가장 짧은 경로를 찾는 알고리즘입니다. 대표적인 알고리즘으로는 "다익스트라 알고리즘"과 "플로이드 워셜"이 있습니다. 이번 포스팅에서는 다익스트라 알고리즘에 대해 설명하겠습니다.

​

​

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

여러 개의 노드가 있는 그래프가 주어지면, 특정한 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구할 수 있는 알고리즘입니다.

알고리즘의 동작과정은 아래 순서로 이루어집니다.

1) 먼저 출발 노드를 설정합니다.

2) 최단 거리 테이블을 초기화해줍니다.

3) 1에서 선택한 노드와 연결되어 있고 방분하지 않은 노드들 중에서  최단 거리가 가장 짧은 노드를 선택합니다.

4) 3에서 선택된 노드를 거쳐 다음 노드로 가는 비용을 모두 계산하여 최단 거리 테이블을 갱신합니다.

5) 3-4과정을 반복해줍니다.

step 1) 출발 노드 1

step 2) 방문하지 않은 노드 중 가장 최된 거리인 4번 노드 선택

이때, 테이블의 3번 노드를 보면 1->3으로 바로 가는 것 보다 1->4->3의 경로를 선택하는 것이 더 적은 비용이 드는 것을 알 수 있습니다. 때문에,  step 1에서 갱신되었음에도 다시 갱신되게 됩니다.

​

step 3) 2번 노드 선택

​

step 4) 5번 노드 선택

​

step 5) 3번 노드 선택

​

step 6) 6번 노드 선택

최종 최단 거리 테이블

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

최종 최단거리 테이블이 의미하는 바는 1번 노드에서 출발 할때 2, 3 ,4, 5, 6번 노드까지 도착하기 위한 최단 경로가 각각 2, 3, 1, 2, 4라는 의미입니다.

 

- 코드(링크)

다익스트라 알고리즘은 힙(heap)을 이용해 구현합니다.

GitHub - jgyy4775/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억으로 설정합니다.

# 노드의 개수, 간선의 개수를 입력받습니다.
n, m = map(int, input().split())

# 시작 노드 번호를 입력받습니다.
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만듭니다.
graph = [[] for i in range(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 dijkstra(start):
    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 = 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):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력하겠습니다.
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력합니다.
    else:
        print(distance[i])