최단 경로(다익스트라)

LONGNEW·2021년 1월 10일
0

여러가지

목록 보기
9/18

다익스트라(Dijkstra)

특정노드에서 출발해 모든 노드로 가는 각각의 최단 경로를 구해주는 알고리즘.
'음의 간선'이 없을 때 정상적으로 동작한다.

동작과정

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

최단 거리 테이블의 경우 각 노드에 대한 최단 경로를 1차원 리스트에 저장하는 것.

구현 방법.

  1. 구현하기 쉽지만 느린 코드
  2. 구현하기에 조금 까다롭지만 빠른 코드👍

최단 거리를 비교 할 때 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하기에 현재 노드 까지 오는 거리, 즉 최단 거리 테이블[현재노드]의 값에 다음 노드로 가는 거리를 합한 것을 비교해야함.

1번 방법

시간 복잡도 O(V^2)

각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언.
단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택' 하기 위해 1차원 리스트의 모든 원소를 확인 한다.

필요 변수 : 간선들의 연결을 나타낼 그래프, 최단 거리 테이블, visit 리스트.
필요 함수 : 간선의 거리가 짧은 것을 찾아줄 함수, 다익스트라 함수.

import sys
INF = 1000000

n , e = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
visit = [False] * (n + 1)
distance = [INF] * (n + 1)

for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))

def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n + 1):
        if distance[i] < min_value and not visit[i]:
            index = i
    return index

def dijkstra(start):
    distance[start] = 0
    visit[start] = True

    for node, cost in graph[start]:
        distance[node] = cost

    for i in range(n - 1):
        now = get_smallest_node()
        visit[now] = True
        for node, wei in graph[now]:
            cost = distance[now] + wei
            if cost < distance[node]:
                distance[node] = cost

dijkstra(start)

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

2번 방법.

1번 방법의 최대 문제는?
'최단 거리가 가장 짧은 노드'를 찾기 위해, 매번 최단 거리 테이블을 하나씩 탐색해야 한것 (이것이 O(V)의 시간을 잡아먹음)

-> 최단 거리가 가장 짧은 노드를 더 빠르게 찾을 수 있다면???
힙 자료구조를 이용하자.

힙 : 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나.
파이썬의 라이브러리 PriorityQueue 혹은 heapq를 이용할 수 있는데 일반적으로, heapq가 더 빠르게 동작한다.

데이터의 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정한다.
ex) (가치, 물건) 으로 입력된다면 '가치' 값이 우선순위 값이 되는것.

최소 힙을 이용하는 경우 힙에서 원소를 꺼내면 '가장 값이 작은 원소'가 추출된다.

heapq 임포트 필요.
필요 변수 : 간선들의 연결을 나타낼 그래프, 최단 거리 테이블
필요 함수 : 다익스트라 함수.

import sys
import heapq
INF = 1000000

n , e = map(int, sys.stdin.readline().split())
start = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now_node = heapq.heappop(q)
        # 경로의 비용이 커서 계속 뒤에 남아있다가 마지막에
        # 들어오는 경우를 걸러내기 위함.
        # visit의 역할도 하는듯 이미 최단 경로가 들어와 있으면
        # 아래의 반복문이 실행될 이유가 없으니.
        if distance[now_node] < dist:
            continue
        for next_dis, next_node in graph[now_node]:
            cost = dist + next_dis
            if distance[next_node] > cost:
                distance[next_node] = cost
                # 현재에서 이동한 다음 노드까지 의 경로는
                # 총합 경로이기에 더한 값이 들어가야 한다.
                heapq.heappush(q, (cost, next_dis))

dijkstra(start)

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

0개의 댓글