알고리즘 - 최단 경로 알고리즘(Shortest algorithm) / 다익스트라 알고리즘

 

<최단 경로 문제>

 

<다익스트라 최단 경로 알고리즘이란?>

# 최단 경로는 DP로 구하는 것이 일반적이지만 다익스트라 최단 경로 알고리즘의 경우엔 그리디 알고리즘으로 분류 된다.

# 3번 문항때문에 우리는 다익스트라 최단 경로 알고리즘을 그리디 알고리즘으로 분류한다.

 

# 출발노드로부터 다른 모든 노드까지의 최단 노드 테이블을 구하는 문제가 출제될 가능성이 높고 모두를 출력하라는 경우는 코테에서 자주 나오지 않는다.

# 1번 노드의 거리가 0인 이유는 자기 자신에게 돌아가는 거리가 0이기 때문이다.

 

<다익스트라 알고리즘의 특징>

# 그리디 알고리즘에 속한다는 것

 

<다익스트라 알고리즘: 간단한 구현 방법>

<다익스트라 알고리즘: 간단한 구현 코드>

import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

#노드의 개수, 간선의 개수를 입력받기
n, m = map(int,input().split())

#시작 노드 번호를 입력받기
start = int(input())

#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
#연결리스트형태로 준비.
graph = [[] for i in range(n+1)]

#방문한 적이 있는지 체크하는 목적의 리스트 만들기
#모든 노드에 대해서 방문하지 않은 것으로 False값을 넣어줌. 
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_value = INF
    index = 0 #가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n+1):
        #방문하지 않은 노드 중에 가장 최단거리가 짧은 노드를 반환하도록 한다. 
        if distance[i] < min_value and not visited[i]:
            min_value = 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]
        #시작 노드를 제외한 전체 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[1] == INF:
        print("INFINITY")
    else:
        print(distance[i])

<다익스트라 알고리즘: 간단한 구현 방법 성능 분석>

 

<다익스트라 알고리즘: 개선된 구현 방법>

# 6번 노드에서 출발하는 간선이 없어서 갱신 X

# 이와 같이 현재 꺼낸 원소의 거리값이 테이블에 저장되어 있는 거리값보다 크다면 이미 방문처리한 것으로 처리해서 넘어가면 된다.

 

<다익스트라 알고리즘: 개선된 방법으로 구현된 코드>

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9) #무한을 의미하는 값으로 10억 설정

#노드의 개수, 간선의 개수를 입력받기
n, m = map(int,input().split())

#시작 노드 번호를 입력 받기
start = int(input())

#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i 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):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q,(0,start)) #리스트 q에 시작노드의 거리를 0으로 넣어주는 작업
    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]))

#다익스트라 알고리즘을 수행
dijkstra(start)

#모든 노드로 가기 위한 최단 거리를 출력
for i in rnage(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    #도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

 

<다익스트라 알고리즘: 개선된 구현 방법 성능 분석>

 

#다익스트라 알고리즘은 음수에 반응하지 않기에 이는 플로이츠로 해결해야 한다.