다익스트라를 구현할 때 일반 큐와 우선순위 큐(힙)으로 구현했을 때의 차이점은 무엇일까
def dikstra(num): # 다익스트라 계산 함수
queue = [num]
while queue:
node = queue.pop(0)
for i in graph[node]:
if distance[i[0]] > distance[node] + i[1]:
distance[i[0]] = distance[node] + i[1]
queue.append(i[0])
일반 큐로 구현했을 때이다. 시작 노드에 연결된 노드를 하나씩 방문하면서 거리를 비교해나간다.
def dikstra(start, destination, n):
distance = [1e9 for _ in range(n+1)]
distance[start] = 0
queue = [[0, start]]
while queue:
w, x = heappop(queue)
if distance[x] < w: continue
global graph
for i in graph[x]:
if distance[i[0]] > distance[x] + i[1]:
distance[i[0]] = distance[x] + i[1]
heappush(queue, [distance[i[0]], i[0]])
우선순위 큐로 구현했을 때이다. 후처리 과정은 똑같지만 전처리를 한다. 자세한 과정은 https://jason9319.tistory.com/307 를 참고하자