[그래프] 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

[그래프] 28. BFS 최단 경로용으로 바꾸기

실습과제 BFS 알고리즘 최단 경로용 bfs의 각 단계는 아래와 같다. 큐에 아무 Node도 없을 때까지: 큐에서 가장 앞 Node를 꺼낸다 이 Node에 인접해 있는 Node들을 돌면서: 처음 방문한 Node면: 방문한 Node로 표시한다 최단 경로용으로 쓸때는 이 부분이 새롭게 추가되는데, predecessor 변수를 설정한다 마지막에 Node를 큐에 넣는다

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

BFS 알고리즘을 이용한 predecessor 방식이 진짜 최단 경로가 맞는지 어떻게 확신할 수 있을까? 이번 장에서는 증명해보겠다. 이것을 이해하기 위해서는 BFS가 Node를 방문하는 순서를 살펴봐야 한다. BFS는 시작 Node 를 먼저 본다. 그리고 이 시작점에서 인접한 Node 들을 모두 방문한다. <img src="/media/post-body/2021/09/27/image_lf2Gceu.png" style="max-width:250px;

[그래프] 26. 최단 경로용 BFS

아래와 같은 빈 큐와 그래프가 있다고 가정하자. 여기에 BFS 알고리즘을 사용할 것이다. 각 Node 의 predecessor 는 보기 편하게 표로 나타내겠다. 먼저 시작점 Node를 방문했다고 표시한다. 시작점은 아무데서도 오지 않았다. 그러니 이전 Node가 없는 것이다. predecessor 는 없다고 표시한다. 시작점 Node A 를 큐에

[그래프] 25. BFS predecessor

BFS를 할 때는 각 Node 는 그 Node 를 방문한 적이 있는지 없는지 표시하는 목적으로 visited라는 변수를 저장한다. 사진에서는 이 visited 를 변수를 Node의 색으로 나타냈다. 최단 경로를 구할 때는 이 visited 변수에 추가로 predecessor 라는 변수도 저장해

[그래프] 24. 최단 경로 알고리즘이란?

최단 경로란? 그래프에서 경로라는 것은 두 Node 사이를 이어주는 길이다. 아래와 같은 그래프가 있다고 가정하자 &#39;지웅&#39;에서 &#39;규리&#39; Node까지 가는 이 길을 보자. 바로 이 길이 지웅 - 소원 - 규리 경로 이다. &#39;지웅&#39;에서 &#39;규리&#39;까지 가는 경로가 하나만 있는 것이 아니다. <img src="/media/post-body/2021/09/27/image_l6YaRr6.png" style="max-width:400px;