[Python]다익스트라_최단경로알고리즘 (feat. heap)

 

다익스트라는 그리디와 DP의 유형으로 분류되는 최단경로 알고리즘이다. 

DP는 계속해서 그래프를 갱신하기 때문이고 그리디는 그 순간 가장 짧은 정점을 선택하기 때문이다. 

 

 

음의 가중치가 적용될 수  없어 일상생활 문제에서 잘 사용될 수 있다.

특정한 한 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘이다. 

 

 

 

원래는 O(V^2)의 시간복잡도를 가진다. ( 리스트 이용, 돌면서 가장 거리가 짧은 노드를 찾는 경우)

이것은 5,000개 까지는 괜찮지만 개수가 10,000개가 되면 시간초과가 될 가능성이 농후하다.

(파이썬은 1초에 2천만 연산이라고 생각하면 됨)

 

 

 

시간초과를 막기 위해서 heap을 이용하면 된다. 

(방문하지 않은 최단거리의 정점을 찾을 때 이용)

파이썬의 minheap은 heappop을 하면 가장 작은 원소를 pop해준다. 

 

 

 

heap을 이용하면 시간복잡도는 O(ElogV)가 된다.

E : 최대 간선의 개수 

V : 노드의 개수 

 

 

 

 

 

백준 최단경로 문제의 답이다. 

코드 : 

def dijkstra(start) :
    #  시작점에서 시작점의 거리는 0
    distance[start] = 0 
    q = []
    
    # 거리는 0, 노드는 start
    heapq.heappush(q,[0,start])
    while q :
        dist, node = heapq.heappop(q)
        # 만약 dist가 현재 있는 거리보다 작으면 실행 X 
        if dist > distance[node] : continue
        
        # node에서 갈 수 있는 정점들을 돌면서 
        for i in mp[node] :
            cost = dist + i[1]
            # 새로운 거리가 원래 길이보다 작다면 
            if cost < distance[i[0]] :
            	# 갱신을 해주고 
                distance[i[0]] = cost 
                # heap에 넣는다.
                heapq.heappush(q,[cost,i[0]])
    
    
if __name__=="__main__" :
    V,E = map(int,input().split())
    k = int(input())
    
    mp = [[] for _ in range(V+1)]
    distance = [int(1e9)] * (V+1)


    for _ in range(E) :
        u,v,w = map(int,input().split())
        mp[u].append([v,w])
    
    dijkstra(k)
    
    for i in range(1,V+1) :
        print("INF" if distance[i] == int(1e9) else distance[i] )

 

 

 

 

 

 

내 관련 포스팅 : 

https://what-am-i.tistory.com/154

[Python/BOJ] 백준 1753 최단경로(다익스트라)

 

무려 1년 2개월 전에 c++로 한번, 8개월 전에 pyfhon으로 풀었었다...

잊어먹었으나 다시 공부하니 할만하다.

역시 사람은 망각의 동물이다😓

 

 

9월 22일날 이 글을 썼는데

10월 14일 또 까먹음... 또 보러옴 🤪

 

 

 

 

 

 

 

출처 : 

[나동빈님 ... 압도적 감사...]

 

https://www.youtube.com/watch?v=F-tkqjUiik0