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

🌱 최단 경로 알고리즘

최단 경로 알고리즘(Shortestest Path)은 가장 적은 비용(Minimum Cost)으로 연결하는 간선들을 찾는 문제입니다.

대표적인 최단 경로 알고리즘 문제로, 다익스트라, 벨만-포트, 플로이드-워셜, A* 알고리즘이 있습니다.

이번 포스팅에서는 다익스트라 알고리즘(Dijkstra) 위주로 공부해볼 예정입니다.

---

🚀 다익스트라 알고리즘 구현하기

다익스트라 알고리즘은 시작노드에서부터 최단 경로를 구하는 알고리즘입니다.

첫번째 문제는 특정노드에서 모든 노드의 최단 경로를 찾는 프로그래머스 - 배달↗ 문제입니다. 문제를 통해 동작 방식을 이해해보도록 하겠습니다.

 

해당 문제는 1번 노드부터 5번 노드까지의 간선과 연결된 노드가 담긴 리스트 `road`와 노드의 갯수 `N` 제한 경로 `K`가 주어지면 제한 경로 안에 있는 최단 경로의 노드의 갯수를 찾는 문제입니다. 

 

1. 먼저 비용 리스트 만들기

최단 경로 문제의 포인트는 먼저 방문여부와 비용(Cost; Distance)를 확인를 확인하는 리스트가 필요하다는 것입니다.

아래와 같이 비용을 계산하는 리스트를 만들고 시작 노드엔 0으로 대입하고 나머지엔 최댓값인 `1e9` or (`float('inf')`)를 넣었습니다.

 

def solution(N, road, K):
    dist = [1e9] * (N+1)
    
    dist[1] = 0
    
    graph = [[] for _ in range(N+1)]
    for r in road:
        graph[r[0]].append([r[2], r[1]])
        graph[r[1]].append([r[2], r[0]])
        
    dijkstra(dist,graph)
    
    # 거리 중 K 이하의 노드의 갯수 반환하기
    return len([i for i in dist if i <= K])

 

2. 방문을 위해 우선순위 큐사용하기

드디어, 지금부터 다익스트라 알고리즘을 적용하는 일입니다.

다익스트라 알고리즘은 우선순위 큐를 이용해 가장 거리가 작은 값부터 추출해야 합니다.

우선순위 큐에 대한 정보는 우선순위 큐 포스트↗에 정리해두었습니다. 파이썬에서는 `heapq` 라이브러리를 사용하면 쉽게 구현할 수 있습니다.

 

1. 먼저 우선순위 큐를 통해 가장 비용이 적은 정점을 꺼내 현재 정점(`node`)으로 설정합니다. (처음엔 1번 노드가 현재 정점일 것입니다.)
2. 현재 정점과 인접한 정점들의 cost 값을 비교하면서 최소값을 갱신하게 됩니다.  (`cost + next_cost < dist[next_node]`)
3. 그 다음, 갱신이 되었다면 갱신된 노드(`next_node`)에 갱신 값을 넣어주고 다시 힙에 추가해주면 됩니다.

1번 Node의 인접한 노드들은 2번과 4번 입니다.

 

2번 노드의 인접 노드인 3번과 5번은 1e9와 비교하여 최소값을 갱신하게 됩니다.

import heapq

def dijkstra(distance, graph):
    
    # 방문할 노드가 저장될 우선순위 큐
    queue = []
    heapq.heappush(queue, [0, 1]) # 시작 노드부터 시작
    
    while queue:
        cost, node = heapq.heappop(queue) # 1
        
        # 이미 방문한 정점의 경우
        if distance[node] == 1e9:
            continue
        
        for next_cost, next_node in graph[node]:
            if cost + next_cost < dist[next_node]: # 2 
                distance[next_node] = cost + next_cost # 2
                heapq.heappush(queue, [cost + next_cost, next_node]) # 3

 

🌱 시간 복잡도

다익스트라 알고리즘 1개의 노드에서 인접한 간선들을 모두 검사하게됩니다.

또, 간선을 검사할 때마다 우선순위 큐를 통해 노드 및 거리를 추가하는 과정이 있습니다.

결론적으로, 간선을 모두 검사하는 과정(`O(E)`)와 거리 정보를 추가하는 과정(`O(log V)`)을 합친 시간 복잡도 입니다.

시간 복잡도

O(E log V)

---

🌱 이외 최단 경로 알고리즘

최단 경로 알고리즘으로는 다익스트라 알고리즘만 있는 것이 아닙니다. 이외에도 플로이드-워셜 알고리즘, A* 알고리즘이 있습니다.

• 플로이드 워셜 알고리즘 : 3중 반복문을 이용해 모든 노드의 최단 거리를 구하는 알고리즘입니다. 
• A* 알고리즘 : 휴리스틱 함수(평가 함수)를 통해 추정거리를 계산하는 알고리즘 입니다. 시간 복잡도는 휴리스틱 함수에 따라 달라지지만 최선 O(E)의 시간에 동작합니다. 
• 벨만 포드 알고리즘 : 음의 가중치가 있는 그래프에서도 사용될 수 있다는 특징이 있습니다. 그러므로 시간 복잡도는 O(V * E) 입니다. 

A*는 다익스트라 알고리즘을 개선한 알고리즘입니다.

📝 풀어보기 좋은 문제들

• 합승 택시 요금(2021 KAKAO BLIND)↗
• [백준 - 5719]거의 최단 경로↗ 
•  

---

☕️ 포스팅이 도움이 되었던 자료

• EBS 링크 소프트웨어 세상, "가장 빠른 길을 찾아라, 최단 경로 알고리즘"
• 배달아~ 배달 가는 길 알려줘!(단호함) - 우아한기술블로그

오늘도 저의 포스트를 읽어주셔서 감사합니다.

설명이 부족하거나 이해하기 어렵거나 잘못된 부분이 있으면 부담없이 댓글로 남겨주시면 감사하겠습니다.