[Algorithm] 최단 경로 (Shortest Path)

최단 경로(Shortest Path)는 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다.

흔히 알고 있는 최단 경로 알고리즘은 다익스트라(Dijkstra)입니다. 플로이드 워셜(Floyd-Warshall) 알고리즘 등도 존재하지만, 본 포스팅에서는 다익스트라만 다루겠습니다.

 

다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류되며, 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하는 것입니다.

 

다익스트라 알고리즘 과정

1. 출발 노드 설정

2. 최단 거리 테이블 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

5. 위 과정에서 3번과 4번을 반복

 

 

위와 같이 노드와 노드 간 거리(간선)를 표현하는 그래프가 주어졌을 때, 우선순위 큐 기반 다익스트라 알고리즘 소스 코드를 작성해 보겠습니다.

import heapq


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]))


INF = int(1e9)  # 무한의 의미: 10억
n = 6           # 노드 수
edge = [
    [1, 2, 2],
    [1, 3, 5],
    [1, 4, 1],
    [2, 3, 3],
    [2, 4, 2],
    [3, 2, 3],
    [3, 6, 5],
    [4, 3, 3],
    [4, 5, 1],
    [5, 3, 1],
    [5, 6, 2]
        ]
m = len(edge)   # 간선 수

graph = [[] for i in range(n + 1)]
# visited = [False] * (n + 1)
distance = [INF] * (n + 1)

for e in edge:
    # a 번 노드에서 b번 노드로 가는 비용이 c
    a, b, c = e[0], e[1], e[2]
    graph[a].append((b, c))

dijkstra(1)

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

우선순위 큐는 FIFO 구조의 일반 큐와 다르게 삽입되는 데이터 가치에 따라 먼저 삭제할 수 있습니다.

우선순위 큐를 최소 힙으로 구현하여 가치자 낮은 데이터를 먼저 삭제할 수 있도록 합니다.

 

 

heapq.heappush(q, (0, start))에서 두 번째 파라미터 (0, start) 튜플은 최단 거리와 노드번호 입니다.

그리고 while문에서 heapq.heappop(q)를 통해 가장 위에 있는 노드, 즉 최단 거리가 가장 짧은 노드에 방문합니다.

현재 방문한 노드를 거쳐 다음 노드로의 거리를 계산하고, 최단 거리 테이블이 갱신될 때 해당 노드의 (최단 거리, 노드) 튜플을 삽입합니다.

 

위 작업을 반복하면 하나의 노드에서 각 노드까지의 최단 거리를 계산할 수 있습니다.

 

참고: https://www.youtube.com/watch?v=acqm9mM1P6o