Dijkstra(다익스트라)

Dijkstra(다익스트라)

- 하나의 노드에서 다른 모든 노드까지의 최단경로를 구하는 알고리즘

- 간선들의 가중치를 기억해서 해당 노드까지의 경로가 최소로 갱신하는 알고리즘

 

import heapq

ex_visit = [0 for _ in range(n+1)] #전의 값을 저장하는 곳
visit = [[''] for _ in range(n+1)] #전체 경로 나타내는 곳

def djikstra(start):
	global ex_visit, visit 
    
    wei = [1000000] * (n+1)  #최단거리
    heap = [] 

    heapq.heappush(heap,(0, start)) #(거리, node)
    wei[s] = 0 
    
    while heap:
    
        weight, node = heapq.heappop(heap)
        
        for we, no in graph[node]:
        
            if wei[no] > weight + we:
                wei[no] = weight + we
                heapq.heappush(heap,(weight+we,no))
                
                ex_visit[no] = node  #역추적하기 위해 전 node를 저장한다.
                visit[no] = visit[node] + ',' + str(no) 
                
                
    return wei
    
    
    

​

 

 

<추가자료>

Minsuk Heo 허민석 유튜브 https://www.youtube.com/watch?v=HFapeLxvdNg