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

O_K·2022년 8월 10일
0

알고리즘

목록 보기
1/2
post-thumbnail

최단경로 알고리즘

그래프상에서 가장 짧은 경로를 찾는 알고리즘

  • 다익스트라 알고리즘(Dijkstra)
  • 플로이드 워셜 알고리즘(Floyd-Warshall)
  • 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

다익스트라(Dijkstra)

한 지점(시작)에서 다른 모든 지점까지의 최단 경로를 계산

  1. 출발 노드 설정
  2. 최단거리 테이블 초기화
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  5. 3-4 반복
  • 우선순위 큐를 사용하여 시간복잡도를 O(V^2)에서
    O(ElogV)(V: 노드개수, E: 간선개수)로 줄일 수 있다.

문제를 통해 구현해보기

백준 1753번 : 최단경로

💡 구현 1 : 순회

import sys
input=sys.stdin.readline

V, E = map(int, input().split())
K = int(input())

INF = int(1e9)
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append([v, w])


dist = [INF]*(V+1)
visited = [False]*(V+1)

# 인접한 노드 중 최단거리를 가지는 노드 반환
def get_smallest():
    min_value = (0, INF)
    for i in range(1, V+1):
        if not visited[i] and dist[i] < min_value[1]:
            min_value = (i, dist[i])
    return min_value[0]


def Dijkstra(start):
    dist[start] = 0
    visited[start] = True

    for (adj_node, weight) in graph[start]:
        # 같은 노드간 여러 간선이 존재할 수 있으므로 if 문을 써준다
        if dist[adj_node] > weight:
            dist[adj_node] = weight

    # 시작 노드를 제외한 다른 모든 노드를 순회
    for _ in range(V-1):
        # 인접 노드 중 최단거리 노드를 방문
        now = get_smallest()
        visited[now] = True
        
        # 기존의 최단거리(시작-인접node) > 현재 방문한 노드를 거친 최단거리(시작-now + now-인접node)
        # 일 경우 최단거리 테이블 갱신
        for (adj_node, weight) in graph[now]:
            cost = dist[now] + weight
            if cost < dist[adj_node]:
                dist[adj_node] = cost

Dijkstra(K)
for i in range(1,V+1):
    print(dist[i] if dist[i] < INF else 'INF')

💡 구현 2 : 우선순위 큐

import sys
import heapq
sys.stdin = open('input.txt')
input=sys.stdin.readline

# 노드 개수, 간선 개수
V, E = map(int, input().split())
# 시작 노드 번호
K = int(input())

INF = int(1e9)
# 노드 연결 정보
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, input().split())
    graph[u].append([v, w])

# 최단거리 테이블
dist = [INF]*(V+1)

def Dijkstra(start):
    q = []
    # (거리, 노드번호)로 heapq에 넣어 거리순으로 정렬되도록 함
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        # now 노드에 오기까지 최단거리, 현재 노드번호
        # heapq를 사용하여 최소힙으로 최단거리 부터 정렬됨
        current_d, now = heapq.heappop(q)

        # 최소힙을 사용하여
        # visited를 사용하지 않아도 최단거리보다 클 경우 continue 하므로
        # 이미 계산됨을 확인할 수 있음
        if dist[now] < current_d:
            continue

        # now 노드와 인접한 노드확인
        for (adj_node, weight) in graph[now]:
            # now 노드까지의 최단거리 + 인접노드 까지 거리
            total_d = current_d + weight
            # 이전 측정한 인접노드까지의 최단거리 > 새로 측정한 최단거리
            # -> 인접노드까지의 최단거리 테이블 갱신
            if total_d < dist[adj_node]:
                dist[adj_node] = total_d
                heapq.heappush(q, (total_d, adj_node))


Dijkstra(K)
for i in range(1,V+1):
    print(dist[i] if dist[i] < INF else 'INF')
profile
즐거운 개발자가 목표

0개의 댓글