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

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

DirectedGraph (방향 그래프)

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

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

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

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

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

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

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

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

graph

September 5, 2023