[알고리즘] 다익스트라

가중치 그래프  구현

graph ={
	1 : [(2, 2), (1, 4)],
    2 : [(1, 3), (9, 5), (6, 6)],
    3 : [(4,6)],
    4 : [(3,3), (5, 7)],
    5 : [(1, 8)],
    6 : [(3, 5)],
    7 : [(7, 6), (9, 8)],
    8 : [],
}

 

다익스트라 구현

 

import heapq

def dijkstra(graph, start, final, n):
	costs = {}
    pq = []
    heapq.heappush(pq, (0, start))
    
    while pq:
    	cur_cost, cur_v = heapq.heappop(pq)
        if cur_v not in costs:
        	costs[cur_v] = cur_cost
            for cost, next_v in graph[cur_v]:
            	next_cost = cur_cost + cost
                heapq.heappush(pq, (next_cost, next_v))
    return costs[final]
    
dijkstra(graph, 1, 8)

 

코드설명

 

dijkstra 알고리즘에 그래프, 시작점, 도착점을 넣어준다.

ex) 1번 노드에서 8번노드까지 최단거리를 구한다.

 

costs는 얼만큼의 비용이 들었는지 값을 입력(각 노드의 최소값을 입력)

pq 는 우선순위큐(값이 가장 작은 값이 우선순위)

 

그다음 세부순서는

1. 우선순위큐에 시작노드 추가.

2. 우선순위가 가장 높은 노드 추출.

3.방문여부 확인

4. 비용 업데이트

5. 현재 노드와 연결된 노드 우선순위 큐에 추가.

6. 목적지에 기록된 비용 반