[이코테]최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘

최단 경로 문제

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

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

이르케 매 순간 더 짧은 경로를 찾아낸다 !
그

다익스트라 알고리즘 : 동작 과정 살펴보기

자 1을 시작점으로 1부터 시작하고 나머지는 무한대로 테이블에 적어주자 !
그리고 1과의 연결되어있는 노드들의 거리를 적어두자 !
그리고 1다음으로 1과 연결된 노드중 제일 ~ 거리가 가까운 노드인 4부터 가서 4와 연결된 노드들을 기준으로 거리를 다시 탐색해주자 !

4를 방문처리하고 이제 방문하지 않은 노드중 최단거리가 젤 짧은 2로 가서 2로부터 거리를 초기화시켜준다!

같은 방식으로 고곡 !
이렇게 쭉 진행하고 나서 마지막 노드는 처리안해도 상관없다.

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

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

• 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차탐색)한다.

다익스트라 알고리즘 : 간단한 구현 방법(python)

# 다익스트라 알고리즘 
import sys
from turtle import distance 
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미 하는 10억 

#노드의 개수, 간선의 개수 입력받기
n,m = map(int,input().split())
# start num 
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기 
graph =[[] for _ in range(n+1)] 
#방문한 적이 있는지 체크하는 목적의 리스트 제작 
visted = [False] * (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 
    idx= 0 # 가장 최단 거리가 짧은 노드 번호 (인덱스) 
    for i in range(1,n+1):
        if (distance[i]<min_value and not visted[i]) : #만약 거리가 최소설정거리(무한)보다 작고, 방문하지 않은 노드라면
            min_value = distance[i]
            idx = i
    return idx 

def dijkstra(start):
    # 시작 노드에 대해 초기화 
    distance[start] = 0
    visted[start] = True 
    for j in graph[start]:
        distance[j[0]] = j[1] #j[0] : b번 노드 j[1]: 비용 
        #start 에서 j[0]번 노드로 가는 비용 j[1]
    #시작 노드를 제외한 전체 n-1개의 노드에 대한 반복 
    for i in range(n-1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리 
        now = get_smallest_node()
        visted[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("도달못함")
    else : #도달할 수 있는 경우 거리를 출력 
        print(distance[i]) 
    

허허
이게 간단한 구현이라니 나는 감자다..

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

저런 문제들을 위해 간단한 구현방법이..아니라 다른 구현방법을 생각해야한다.
그를 위해 우선순위 큐를 배우고가자

우선순위 큐

힙

리스트보다 훠얼~~~ 빅오가 낫다
힙은 트리구조인 자료구조이다

힙 라이브러리 사용 예제 : 최소 힙

import heapq 

#오름차순 힙 정렬 
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...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(reuslt)
#[9,8,7...1,0]

value를 -붙여서 값을 반대로 만들군,.!

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

다익스트라 알고리즘 : 동작 과정 살펴보기(우선순위 큐)

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

# 다익스트라 알고리즘 
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미 하는 10억 

#노드의 개수, 간선의 개수 입력받기
n,m = map(int,input().split())
# start num 
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):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입 
    heapq.heappush(q,(0,start))
    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 range(1,n+1):
    if distance[i]==INF:
        print("못감")
    else:
        print(distance[i])

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