# [ 최단경로 찾기 ] by Python
스타크래프트를 하다가 유닛이 어떻게 장애물을 피해 최단경로를 찾아서 갈까 궁금해 하다가 최단경로 찾는 방법을 검색하던 중 가중치 그래프를 이용한 다익스트라 알고리즘을 설명하는 글을 보고 그대로 한번 파이썬으로 짜봤다.
다익스트라(Dijkstra) 알고리즘
① 지도상의 모든 건물들과 집에서 각 건물들까지의 최단 거리를 나타내는 표를 만든다.
② 집과 직접 길로 이어진 건물들까지의 최단 거리는 지도에 표시된 값으로 적고 그렇지 않은 건물들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다.
③ 거리가 가장 짧은 건물부터 긴 건물 순으로 방문하고 방문한 건물은 색깔로
칠해 구별한다. 이때 방문한 경로도 색칠한다.
④ 새로운 건물을 방문하면 그 건물과 이어진 건물들까지의 거리를 새로 바꾼다. 단, 이전에 이미 최단 거리가 구해졌었다면 거리를 서로 비교해 작은 것으로 바꾸거나 유지한다.
⑤ 그래프의 모든 건물들을 방문할 때까지 ③,④의 과정을 반복한다.
출처 : //playsw.naver.com/repo/cast/105
#대략적인 알고리즘 과정
#자세한 알고리즘 설명(영어)
# 구현소스
+)설명추가
#최단경로 알고리즘 #reference : //navercast.naver.com/contents.nhn?rid=2871&contents_id=85293 import copy #목적지와 도착지를 설정해준다 departure = 'home' destination = 'school' print "-----------[", departure, "->", destination,"]----------" #① 지도상의 모든 건물들과 집에서 각 건물들까지의 최단 거리를 나타내는 표를 만든다. landscape = { 'home': {'hairShop':5, 'superMarket':10, 'EnglishAcademy':9}, 'hairShop' : {'home':5 ,'superMarket':3, 'bank':11}, 'superMarket' : {'hairShop':3, 'home':10, 'EnglishAcademy':7, 'restourant':3}, 'EnglishAcademy': {'home':9, 'superMarket':7, 'school':12}, 'restourant' : {'superMarket':3, 'bank':4}, 'bank' : {'hairShop':11, 'restourant':4, 'EnglishAcademy':7, 'school':2}, 'school' : {'bank':2, 'EnglishAcademy':12} } routing = {} for place in landscape.keys(): routing[place]={'shortestDist':0, 'route':[], 'visited':0} #④ def visitPlace(visit): routing[visit]['visited'] = 1 for toGo, betweenDist in landscape[visit].items(): toDist = routing[visit]['shortestDist'] + betweenDist if (routing[toGo]['shortestDist'] >= toDist) or not routing[toGo]['route']: routing[toGo]['shortestDist'] = toDist routing[toGo]['route'] = copy.deepcopy(routing[visit]['route']) routing[toGo]['route'].append(visit) #② 집과 직접 길로 이어진 건물들까지의 최단 거리는 지도에 표시된 값으로 적고 그렇지 않은 건물들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다. visitPlace(departure) """ ③ 거리가 가장 짧은 건물부터 긴 건물 순으로 방문하고 방문한 건물은 색깔로 칠해 구별한다. 이때 방문한 경로도 색칠한다. ④ 새로운 건물을 방문하면 그 건물과 이어진 건물들까지의 거리를 새로 바꾼다. 단, 이전에 이미 최단 거리가 구해졌었다면 거리를 서로 비교해 작은 것으로 바꾸거나 유지한다. ⑤ 그래프의 모든 건물들을 방문할 때까지 ③,④의 과정을 반복한다. """ while 1 : #③ minDist = max(routing.values(), key=lambda x:x['shortestDist'])['shortestDist'] toVisit = '' for name, search in routing.items(): if 0 < search['shortestDist'] <= minDist and not search['visited']: minDist = search['shortestDist'] toVisit = name #⑤ if toVisit == '': break #④ visitPlace(toVisit) print "["+toVisit+"]" print "Dist :", minDist print "\n", "[", departure, "->", destination,"]" print "Route : ", routing[destination]['route'] print "ShortestDistance : ", routing[destination]['shortestDist']맵은 한 곳에서 갈 수 있는 모든 지점과 거리를 dict로 나태냄.
# 실행결과
-INPUT
위 그림에서 집에서부터 학교까지의 최단거리를 구하는 것.
출발점 - 집
도착점 - 학교
departure = 'home'
destination = 'school'
-OUTPUT
>>> ================================ RESTART ================================ >>> -----------[ home -> school ]---------- [hairShop] Dist : 5 [superMarket] Dist : 8 [EnglishAcademy] Dist : 9 [restourant] Dist : 11 [bank] Dist : 15 [school] Dist : 17 [ home -> school ] Route : ['home', 'hairShop', 'superMarket', 'restourant', 'bank'] ShortestDistance : 17# 과제
동영상 처럼 지하철 노선도를 가지고 최단 경로 찾기 만들기