[Python, 파이썬] 다익스트라 알고리즘 직접 구현해보기

파이썬으로 다익스트라 알고리즘을 직접 구현해보았다.
다익스트라 알고리즘은 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.

위키피디아 나무위키

DirectedGraph (방향 그래프)

다익스트라 알고리즘을 적용할 그래프를 만들 기 위해
먼저 DirectedGraph (방향 그래프) 를 구현하였다.

 

	class DirectedGraph:
	def __init__(self):
	self.nodes = set()
	self.edges = {}
	def add_node(self, node):
	self.nodes.add(node)
	def add_edge(self, start, end, distance):
	if start in self.nodes and end in self.nodes:
	if start in self.edges:
	self.edges[start].append((end, distance))
	else:
	self.edges[start] = [(end, distance)]
	else:
	print("노드가 존재하지 않습니다.")
	def __str__(self):
	result = "노드: {}\n엣지: ".format(self.nodes)
	for start, end_list in self.edges.items():
	for end, distance in end_list:
	result += "({}, {}, {}) ".format(start, end, distance)
	return result

view raw DirectedGraph.py hosted with ❤ by GitHub

 

다익스트라 알고리즘 (Dijkstra algorithm ) 구현

나무 위키에 단계별로 이미지와 함께 설명이 잘 되어있어 그대로 옮겼더니 정상적으로 동작하였다.

 

	class Dijkstra:
	# 초기화
	# S는 방문한 노드가 아직 없으므로 공집합 상태이다.
	# D는 아직 확인되지 않은 거리는 전부 초기값을 무한으로 잡는다.
	# Q는 방문하지 않은 노드들의 집합이므로, 초기화할 때는 모든 노드들의 집합이 된다.
	S = set()
	d = {}
	Q = set()
	@classmethod
	def find_shortest_path(cls, graph, source):
	for node in graph.nodes:
	cls.Q.add(node)
	cls.d[node] = 0 if node == source else float('inf')
	cls.calc_neighbor_distance(graph, source)
	return cls.d
	# 루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.
	@classmethod
	def calc_neighbor_distance(cls, graph, source):
	neighbor = []
	# 이웃 노드를 방문하고 거리를 계산한다.
	for start, end_list in graph.edges.items():
	for end, distance in end_list:
	if start == source:
	sum = cls.d[source] + distance
	if cls.d[end] == float('inf'): # 첫 방문일 경우에는 값을 갱신한다.
	cls.d[end] = sum
	elif cls.d[end] > sum: # 첫 방문이 아닐 경우에는 최소 경로일 경우에만 값을 갱신한다.
	cls.d[end] = sum
	neighbor.append(end) # 이웃 노드는 임시 큐에 저장하여 보관한다.
	# 완료된 노드는 집합 Q 에서 제거하고 집합 S 에 추가한다.
	cls.Q.remove(source)
	cls.S.add(source)
	# 이웃 노드에서 동일한 작업을 반복한다.
	for node in neighbor:
	if node not in cls.S:
	cls.calc_neighbor_distance(graph, node)

view raw Dijkstra.py hosted with ❤ by GitHub

 

python에서 static method 구현하기

관련해서 찾아보니 classmethod 와 staticmethod 에 대한 이야기가 나왔다.

나는 classmethod 를 이용해서 Dijkstra.find_shortest_path(graph, "A") 형태로 명령어를 호출할 수 있도록 구현하였다.

구현하면서 특이했던 것은 클래스 내의 변수, 메소드에 접근하려면 모두 cls 를 통해서 접근해야 했던 점인 것 같다.

자세한 이야기는 위키 독스의 class 정리 - 정적메소드 @classmethod와 @staticmethod의 정리 를 참고하면 좋을 것 같다.

 

데이터 셋 구성 및 실행

출력값도 gist에서 확인 가능하다.

나무위키에 있는 아래의 그래프를 기준으로 데이터 셋을 구성하였다.

	from DirectedGraph import DirectedGraph
	from Dijkstra import Dijkstra
	# 방향 그래프 생성
	graph = DirectedGraph()
	# 노드 추가
	graph.add_node("A")
	graph.add_node("B")
	graph.add_node("C")
	graph.add_node("D")
	graph.add_node("E")
	graph.add_node("F")
	# 엣지 추가
	graph.add_edge("A", "B", 10)
	graph.add_edge("A", "C", 30)
	graph.add_edge("A", "D", 15)
	graph.add_edge("B", "E", 20)
	graph.add_edge("C", "F", 5)
	graph.add_edge("D", "C", 5)
	graph.add_edge("D", "F", 20)
	graph.add_edge("E", "F", 20)
	graph.add_edge("F", "D", 20)
	# 그래프 출력
	print(graph)
	# Dijkstra 알고리즘 결과 출력
	print(Dijkstra.find_shortest_path(graph, "A"))
	# 출력값
	# 노드: {'C', 'A', 'F', 'D', 'E', 'B'}
	# 엣지: (A, B, 10) (A, C, 30) (A, D, 15) (B, E, 20) (C, F, 5) (D, C, 5) (D, F, 20) (E, F, 20) (F, D, 20)
	# {'C': 20, 'B': 10, 'F': 25, 'D': 15, 'E': 30, 'A': 0}

view raw main.py hosted with ❤ by GitHub

 

최종 코드

https://gist.github.com/dev-jonghoonpark/531baf9ae9aa302ff0d93cea6218092e