[그래프] 33. Dijkstra 구현하기

from collections import deque class Node: def __init__(self, name): self.name = name self.adjustment = [] self.completed = False self.distance = float("inf") self.predecessor = None def add_connection(self, node, weight): self.adjustment.append({"node": node, "weight": weight}) node.adjustment.append({"node": self, "weight": weight}) def backtracking(self): destination_node = self.predecessor shortest_path = f"{self.name}" while destination_node: shortest_path =

[그래프] 32. Dijkstra로 찾은 경로가 최단 경로인 이유

Dijkstra 알고리즘을 이해하려면, 먼저 최단 경로의 성질을 이해해야 한다. 이 성질에 대해서 알아본 다음에 Dijkstra 알고리즘으로 구한 경로가 왜 최단 경로인지 알아보자. 최단 경로 문제와 최적 부분 구조(Optimal Substructure) Dijkstra 로 구한 경로가 왜 최단 경로인지 보기 전에 먼저 최단 경로의 중요한 성질 하나를 짚고 넘어가자.

[그래프] 31. Dijkstra 알고리즘

가중치 그래프에서 최단 경로를 구해주는 Dijkstra 알고리즘에 대해 본격적으로 알아보자. Dijkstra 를 이용할 때는 distance 와 predecessor 그리고 complete 변수를 저장해 줘야한다. distance 와 predecessor 는 표로 그리고 complete 변수는 Node의 색으로 나타내겠다. 알고리즘을 시작하기 전에는 각 Node까지의 경로가 있는지, 또 경로가 있으면

[그래프] 30. 엣지 Relaxation

Dijkstra 알고리즘에서는 Node를 하나씩 방문한다. Node들을 방문하면서 해당 Node의 distance predecessor 변수들을 업데이트 해준다. 이것을 relaxation 동사로는 relax 라고 한다. 좀 더 정확히는 A 에서 B 를 방문할 때, B 의 변수를 업데이트해주는 것을 "엣지 (A, B) 를 relax 한다." 라고 표현한다. 아래

[그래프] 29. Dijkstra 알고리즘 변수들

가중치 그래프에서는 Dijkstra 알고리즘으로 최단 경로를 찾을 수 있다. Dijkstra 알고리즘을 사용하기 위해서는 그래프 Node 에 3가지 변수를 저장해야 한다. 1 번째는 distance 2 번째는 predecessor 3 번째는 complete 이번 장에서는 이 변수들이 각각 어떤 역할을 하는지 알아보겠다. distance 설명 distance 변수는 시작점에서 이 Node