최단경로 알고리즘(다익스트라 파이썬)

최단경로 알고리즘엔 크게 두가지 종류가 있다

1. 한지점 -> 다른지점 최단경로

2. 모든지점 -> 다른 모든지점 최단경로

 

1번은 주로 다익스트라를 이용해서 풀고

2번은 플로이드 워셜 을 이용해서 푼다고 한다

 

근데 나는 어려운건 잘 못해서 오늘은 다익스트라만 하려고 한다

다익스트라 알고리즘

---

알고리즘에서는 그리디로 분류한다

한마디로 모든곳을 방문방문 하면서 제일 작은 값을 찾아내는 거임

 

과정은 

1) 출발 노드 설정

2) 최단거리 테이블을 초기화

3) 방문하지 않은 노드 중에서 최단거리가 짧은 노드 선택

4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신

5) 위 과정에서 3과 4를 반복

 

이 과정을 그림으로 이해해보자 (발그림 ㅈㅅㅈㅅ)

나름 열심히 써봤는데 .. 암튼 이런 과정을 거친다

 

파이썬으로는 두가지 방법을 이용해서 구현 가능한데 

1)구현이 쉽지만 느린 코드 (5000개 이상의 노드면 동작시간 넘 오래걸림)

2) 구현 어렵지만 빠른코드

 

#간단한 다익스트라 알고리즘
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int,input().split())
start = int(input()) #시작노트
graph = [[] for i in range(n+1)] #노드들에 대한 정보 담기
visited = [False] * (n+1) #모두 방문 안함으로
distence = [INF] * (n+1)

for _ in range(m):  #간선 정보 입력받기
    a,b,c = map(int,input().split()) #a에서 b로 가는 비용이 c 라는 의미
    graph[a].append((b,c))

def get_small_node():
    min_val = INF
    index = 0
    for i in range(1,n+1):
        if distence[i] < min_val and not visited[i]:
            min_val = distence[i]
            index = i
    return index

def di(start): 
    #시작노드에 대해서 초기화
    distence[start] = 0
    visited[start] =  True
    for j in graph[start]:
        distence[j[0]] = j[1]
    for i in range(n-1):
        #현재 최단거지가 가장 짧은 노드 꺼내서 방문
        now = get_small_node()
        visited[now] = True
        for j in graph[now]: #현재 노드와 연결된 다른 노드 확인
            cost = distence[now] + j[1]
            if cost < distence[j[0]]: #현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
                distence[j[0]] = cost
di(start)

for i in range(1,n+1):
    if distence[i]== INF:
        print('NO')
    else:
        print(distence[i])

#개선된 다익스트라 알고리즘
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int,input().split())
start = int(input())
#노드들의 정보를 담기
graph = [[] for i in range(n+1)]
#최단 거리 테이블을 모두 무한으로 초기화
distence = [INF] * (n+1)

for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))

def di(start):
    q = []
    heapq.heappush(q,(0,start)) #큐에 삽입
    distence[start] = 0
    while q: #큐가 비어있지 않다면
        #가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist,now = heapq.heappop(q)
        #현재 노드가 이미 처리된 적이 있으면 무시
        if distence[now] < dist:
            continue
        #현재 노드와 인접한 노드를 확인
        for i in graph[now]:
            cost = dist + i[1]
            #현재를 거쳐서 다른 노드로 이동하는게 더 짧은 경우
            if distence[i[0]] > cost:
                distence[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))
di(start)

for i in range(1,n+1):
    if distence[i] == INF:
        print('NO')
    else:
        print(distence[i])

 

이렇게 두가지 방법으로 구현이 가능하다 ! 소스코드 많이 반복해서 써보며 숙지하면 좋을것같다