# [ 최단경로 찾기 ] by Python 스타크래프트를 하다가 유닛이 어떻게 장애물을 피해 최단경로를 찾아서 갈까 궁금해 하다가 최단경로 찾는 방법을 검색하던 중 가중치 그래프를 이용한 다익스트라 알고리즘을 설명하는 글을 보고 그대로 한번 파이썬으로 짜봤다. 다익스트라(Dijkstra) 알고리즘① 지도상의 모든 건물들과 집에서 각 건물들까지의 최단 거리를 나타내는 표를 만든다. 출처 : http://playsw.naver.com/repo/cast/105 #대략적인 알고리즘 과정 #자세한 알고리즘 설명(영어) # 구현소스 +)설명추가
맵은 한 곳에서 갈 수 있는 모든 지점과 거리를 dict로 나태냄. # 실행결과 -INPUT 위 그림에서 집에서부터 학교까지의 최단거리를 구하는 것. 출발점 - 집 도착점 - 학교 departure = 'home' destination = 'school' -OUTPUT
# 과제 동영상 처럼 지하철 노선도를 가지고 최단 경로 찾기 만들기 |