dijkstra 알고리즘 - 스타벅스로 가는 가장 짧은 길이 어떻게 되죠?
안녕하세요. 오늘은 dijkstra 알고리즘을 공부하려고 합니다.
dijkstra 알고리즘은 시작 노드와 목적 노드가 주어지면 이 둘 사이의 최단 경로를 구하는 알고리즘입니다.
자세히 살펴볼까요?
1. dijkstra 알고리즘이란
dijkstra 알고리즘은 네덜란드의 컴퓨터 과학자인 에츠허르 다익스트라(Edsger Wybe Dijkstr) 선생님이 고안한 경로 계획 알고리즘으로 그래프 탐색 이론의 시초라고 할 수 있습니다.
- 컴퓨터 과학을 공부하다보면 dijkstra 선생님의 영향력을 실감할 수 있습니다 ㄷㄷ
2. dijkstra 알고리즘 pseudocode
dijkstra 알고리즘은 각 노드별로 최단 경로를 관리합니다.
노드들을 탐색하면서 인접한 노드들의 최단 경로를 갱신하는데, 이 때 한번 방문한 노드는 다시 방문하지 않는 것이 중요합니다.
pseudo code는 다음과 같습니다.
def dijkstra(graph, start_node_id, end_node_id):
path_map = {start_node_id:([start_node_id], 0)}
queue = [start_node_id]
while len(queue) > 0 and not graph.get_node(end_node_id).is_visited:
node = graph.get_node(queue.pop(0))
graph.set_node_visited(node.id)
previous_path = path_map[node.id]
for edge in graph.get_adjacent_edges(node.id):
other_node = edge.get_other_node(node.id)
_, old_cost = path_map.get(other_node.id, ([], float("inf")))
new_cost = previous_path[1] + edge.weight
if old_cost > new_cost:
path_map[other_node.id] = (previous_path[0] + [other_node.id], new_cost)
if not other_node.is_visited:
queue.append(other_node.id)
return path_map.get(end_node_id, ([], float("inf")))
3. 그림으로 살펴보는 예제
pseudo code도 살펴봤으니 그림 예시로 살펴볼까요?
준비한 그래프는 다음과 같습니다! 자주 보네요 ㅋㅋㅋ
그래도 이번에는 엣지에 weight이 추가되었다는 것이 다릅니다.
dijkstra 알고리즘을 적용하여 노드 1에서 노드 6으로 최단 경로를 찾는 과정을 살펴보도록 하겠습니다.
예제 코드
from dataclasses import dataclass
from typing import List
STAGE = 1
@dataclass
class Node:
id: int
is_visited: bool = False
@dataclass
class Edge:
start_node: Node
end_node: Node
weight: float
def get_weight(self) -> float:
return self.weight
def get_other_node(self, node_id: int) -> Node:
if self.start_node.id == node_id:
return self.end_node
else:
return self.start_node
@dataclass
class Graph:
nodes: dict
adjacent_edges: dict
def get_node(self, node_id: int) -> Node:
return self.nodes[node_id]
def set_node_visited(self, node_id: int):
self.nodes[node_id].is_visited = True
def get_connected_nodes(self, node_id: int) -> List[Node]:
adjacent_edges = self.adjacent_edges.get(node_id, [])
return [edge.get_other_node(node_id) for edge in adjacent_edges]
def get_adjacent_edges(self, node_id: int) -> List[Edge]:
return self.adjacent_edges.get(node_id, [])
def set_edge_weight(self, edge_id: int, weight: float):
self.edges[edge_id].set_weight(weight)
def dijkstra(graph, start_node_id, end_node_id):
path_map = {start_node_id:([start_node_id], 0)}
queue = [start_node_id]
while len(queue) > 0 and not graph.get_node(end_node_id).is_visited:
node = graph.get_node(queue.pop(0))
graph.set_node_visited(node.id)
previous_path = path_map[node.id]
for edge in graph.get_adjacent_edges(node.id):
other_node = edge.get_other_node(node.id)
_, old_cost = path_map.get(other_node.id, ([], float("inf")))
new_cost = previous_path[1] + edge.weight
if old_cost > new_cost:
path_map[other_node.id] = (previous_path[0] + [other_node.id], new_cost)
if not other_node.is_visited:
queue.append(other_node.id)
return path_map.get(end_node_id, ([], float("inf")))
if __name__ == "__main__":
nodes = {}
for i in range(6):
nodes[i+1] = Node(id=i+1)
adjacent_edges = {}
adjacent_edges[1] = [Edge(start_node=nodes[1], end_node=nodes[2], weight=1)]
adjacent_edges[1] += [Edge(start_node=nodes[1], end_node=nodes[3], weight=1)]
adjacent_edges[2] = [Edge(start_node=nodes[2], end_node=nodes[4], weight=1)]
adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[5], weight=1)]
adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[6], weight=10)]
adjacent_edges[3] = [Edge(start_node=nodes[3], end_node=nodes[4], weight=1)]
adjacent_edges[5] = [Edge(start_node=nodes[5], end_node=nodes[6], weight=1)]
graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
print(dijkstra(graph, 1, 6))
실행 결과
※번외
만약 노드 2에서 노드 6으로 바로 가는 엣지의 weight이 10으로 늘어나면 어떻게 될까요?
([1, 2, 5, 6], 3) 이라는 결과가 나와야합니다. 엣지의 weight을 수정하고 다시 실행해볼까요?
dijkstra 알고리즘은 어떠셨나요? 이번에는 하나의 (시작 노드, 목적 노드) 쌍만 해결하는 알고리즘이었는데요.
다음에는 여러 쌍에 대한 최단 경로를 찾아내는 알고리즘들을 공부해보겠습니다.
더 공부하고 싶으신 내용이나 부족한 부분 알려주시면 보완하도록 하겠습니다.
감사합니다 👍