Algorithm 13. Dijkstra's Algorithm

Algorithm 13. Dijkstra's Algorithm

다익스트라 알고리즘

유형

최단 경로

그리디, DP

방식

0에서 시작, 테이블 거리 초기값은 무한 자신하고 연결되고, 방문하지 않는 노드 비용을 갱신한다.

거쳐온 노드들을 더해서 갱신해준다.

갱신 전 값이 작으면 유지한다. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택

구현

방문 테이블 시작 지점은 0, 나머지 초기값은 무한

방문 거리 = 현재까지 거리 + 연결거리 (어차피 현재까지 거리가 최소임) 자료구조 : 힙 (현재 위치, 비용)

추가할 때는 (목적지, 비용)이 됨

next_cost = current_cost + cost 탐색 while 큐가 있을때

for문으로 한바퀴 돌면서, 연결되어 있는 점이 있는 지 확인

연결되는 점이 있으면 큐에 추가

from heapq import heappop, heappush def solution(): table = [float('inf')] * (점의 개수 + 1) table[1] = 0 queue = [(1, 0)] while queue: heappop(queue) for: # 탐색 if #연결: heappush(queue, (node, value))

배달

해설

무방향 무방향이기 때문에, 목적지에서 출발지 비용도 계산해야한다. 예를 들어, 2 - 3이 연결된 경우에 입력값이 3 -> 2 만 들어올 수도 있기 때문에 반대로도 구해야함.

코드

from heapq import heappop, heappush def solution(N, road, K): table = [float('inf')] * (N + 1) table[1] = 0 queue = [(1, 0)] while queue: current, current_cost = heappop(queue) for start, end, cost in road: next_cost = current_cost + cost if start == current and next_cost < table[end]: table[end] = next_cost heappush(queue, (end, next_cost)) elif end == current and next_cost < table[start]: table[start] = next_cost heappush(queue, (start, next_cost)) return len([i for i in table if i <= K])

from http://jooseop.tistory.com/63 by ccl(A) rewrite - 2021-08-24 11:00:15