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

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

위키피디아 나무위키

DirectedGraph (방향 그래프)

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

 

 

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

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

 

 

python에서 static method 구현하기

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

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

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

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

 

데이터 셋 구성 및 실행

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

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

 

최종 코드

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