최단 경로 (Shortest Path Problem) : 다익스트라 알고리즘

최단 경로 알고리즘 이란?

가장 짧은 경로를 찾는 알고리즘
길 찾기 문제라고도 부른다.

✔ 다양한 문제 상황에 사용

한 지점에서 다른 한 지점까지의 최단 경로 (single-pair)
한 지점에서 다른 모든 지점까지의 최단 경로 (single-source)
한 지점으로 가는 모든 최단 경로 (single-destination)
모든 지점에서 다른 모든 지점까지의 최단 경로 (all-pair)

각 지점은 그래프에서 노드로 표현
지점 간 연결된 도로는 그래프에서 간선으로 표현

최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 등이 있다.

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

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든노드까지의 최단 거리를 구하는 알고리즘
그리디 알고리즘으로 분류
→ 매번 가장 비용이 적은 노드 선택 ⭐
최단 거리 테이블 : 각 노드에 대한 현재까지의 최단 거리 정보 저장하고 계속 갱신해 나간다.
우선순위 큐를 사용하는 너비 우선 탐색

알고리즘의 원리

출발 노드를 설정한다.
최단 거리 테이블을 초기화 한다.
방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
위의 과정에서 3, 4번을 반복

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 ‘각 노드에 대한 현재까지의 최단 거리’ 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신하며, 방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인하여 선택하는 알고리즘이다.

다익스트라 알고리즘 동작 과정

1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제

출발 노드 : 1

초기 상태에서는 다른 모든 노드로 가는 최단 거리를 ‘무한’ 으로 초기화 한다.

Step 0 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택

- 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발 노드가 선택

Step 1 현재 노드에서 다른 노드로 가는 비용 계산

- 1번 노드를 거쳐 다른 노드로 가는 비용을 계산

→ 1번 노드와 연결된 모든 간선을 하나씩 확인

Step 2 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 4번 노드

- 4번 노드를 거쳐서 갈 수 있는 노드와 비용을 확인

2(1+1)이다. 이 두 값은 기존의 리스트에 담겨 있던 값보다 작으므로 다음처럼 리스트가 갱신된다.

Step 3 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 2번 노드

- 2번과 5번 노드까지의 최단 거리가 2로 값이 같은데, 이럴때는 일반적으로 번호가 작은 노드를 선택

Step 4 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 5번 노드

- 현재 5번 노드까지 가는 최단 거리가 2이므로 5번 노드에서 3번 노드로 가는 거리인 1을 더한 기존값인 4보다 작기 때문에 새로운 값 3으로 갱신된다. 또한 6번 노드로 가는 거리도 마찬가지로 4로 갱신된다.

Step 5 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 3번 노드

- 5번에서 최단거리인 3번을 선택한다.

Step 6 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 → 6번 노드

- 방문하지 않은 6번 노드를 방문

최종 최단 거리 테이블

: 1번 노드에서 출발했을때, 2번까지 2, 3번까지 3, 4번까지 1, 5번까지 2, 6번까지 4라는 의미

✔ 구현

입력 예시

6 11

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

출력 예시

첫번째 줄은 노드와 간선의 개수

두번째 줄은 시작 노드

세번째 줄은 a b c 일 때, a → b의 비용 c를 의미한다.

방법 1) 간단한 다익스트라 알고리즘

- 매번 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 탐색하기 위해 최단 거리 리스트 순차 탐색

- 시간 복잡도 : → V는 노드의 개수
→ 일반적으로 전체 노드의 개수가 5000개 이하일때만 사용 가능

mport sys
input = sys.stdin.readline
INF = int(1e9)

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():
    min_val = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_val and not visited[i]:
            min_val = distance[i]
            index = i
    return index

def dijkstra(start):
    #시작 노드 처리
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]

    for i in range(1, 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("INF")
    else:
        print(distance[i])

방법 2) 개선된 다익스트라 알고리즘

- 가장 최단거리가 짧은 노드를 선형적으로 찾는게 아닌 Heap을 이용해서 처리

→ 우선순위 큐에 더 짧은 경로를 찾은 노드 넣고, 꺼낼때는 해당 노드를 방문한 적이 있으면 무시, 아니면 처리해주면 된다.

- 시간 복잡도 : → V는 노드의 개수, E는 간선의 개수

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split()) #노드 개수, 간선 개수
start = int(input()) #시작 노드
graph = [[] for _ 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):
    #시작 노드 처리
    pq = []
    heapq.heappush(pq, (0, start))
    distance[start] = 0

    while pq:
        dist, now = heapq.heappop(pq)

        #현재 노드가 이미 처리된 적 있는 노드면,
        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(pq, (cost, i[0]))

dijkstra(start)

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

우선순위 큐(Priority Queue)

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 높은 물건 데이터부터 꺼내서 확인해야하는 경우에 우선순위 큐를 이용할 수 있다
Python, C++, Java를 포함한 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

힙(Heap)

우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나
최소 힙(Min Heap) 과 최대 힙(Max Heap) 이 있다
다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용

우선순위 큐 구현 방식	*삽입 시간*	*삭제 시간*
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

# 최소 힙

import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# 최대 힙

import heapq

# 오름차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

#  [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

'알고리즘 > 기타 알고리즘' 카테고리의 다른 글

최단 경로 (Shortest Path Problem) - 플로이드 워셜 알고리즘 (0)	2022.01.24
재귀함수 Recursion Funtion (0)	2022.01.24
[이것이 코딩 테스트다 with Python] 개미 전사 : Dynamic Programming (0)	2022.01.24
[이것이 코딩 테스트다 with Python] 1로 만들기 : Dynamic Programming (0)	2022.01.24
Dynamic Programming 동적 프로그래밍 (0)	2022.01.24