최단거리 경로찾기, 다익스트라 알고리즘

 
roadMap={
    'home':{'hair':5, 'super':10, 'academy':9},
    'hair':{'home':5, 'super':3, 'bank':11},
    'super':{'home':10, 'hair':3, 'academy':7, 'restourant':3,'bank':10},
    'academy':{'home':9,'super':7,'bank':7,'school':12},
    'restourant':{'super':3,'bank':4},
    'bank':{'hair':11,'restourant':4,'super':10,'academy':7,'school':2},
    'school':{'bank':2,'academy':12}
}
### fastWay={place:[visit, lenth, whereBefore]}
fastWay={}
for i in roadMap.keys():
    fastWay[i]=[0, 99999999, 0]#{home:[1, 0, home]
#print(fastWay)

def findNext():#place명으로 안에서 dic을 가공하는게 나을지도 -> 함수 안에서 visit을 1로 하는게 이상적일듯 -> 전체경로중 방문하지 않은 가장 작은걸 스캔하는거였음
    nextPlace='noWay'
    min=99999999
    for i in fastWay.keys():
        if fastWay.get(i)[0]==0 and min > fastWay.get(i)[1]:
            nextPlace=i
            min=fastWay.get(i)[1]
    return nextPlace
def markingPath(place):#내가 어디서 왔는지도 써야하는데.. 최초 시작점은 반복문 밖에 before을 0으로 하여 경로추적시 0에서 끝나게
    #fastWay.get(place)[2]=before
    for i in roadMap.get(place).keys():#방문한곳엔 마킹하면 안됨, 기존에 있던 lenth보다 자기의 lenth+그곳으로 가는 lenth가 낮으면 마킹
        if fastWay.get(i)[0]==0 and fastWay.get(i)[1] > fastWay.get(place)[1] + roadMap.get(place).get(i):
            fastWay.get(i)[1] = fastWay.get(place)[1] + roadMap.get(place).get(i)
            fastWay.get(i)[2] = place

#start='home'
start=input('시작점을 입력하세요 : ')
finish=input('도착점을 입력하세요 : ')
fastWay.get(start)[0]=1#최초 시작점 방문처리
fastWay.get(start)[1]=0#최초 시작점 거리0
fastWay.get(start)[2]='start'
markingPath(start)                #print()

while True:                                             #거리 마킹
    move = findNext() # 다음 가야할곳은 hair
    if move=='noWay':break
    fastWay.get(move)[0]=1#vist
    markingPath(move)
    #start=move
rootWay=[]
result=''
lenth=fastWay.get(finish)[1]
while True:                                             #경로 작성
    if finish=='start':break
    #print(finish)
    rootWay.append(finish)
    finish=fastWay.get(finish)[2]
#시작점에서 marking path를 하고 전체중에 제일 짧은곳을 scan한다음(findNext) 다시 그곳에서 marking!
while rootWay:
    result += rootWay.pop()+' '

print('최단경로는 : ' + result + ' 거리는 : ' + str(lenth))
print(fastWay)

 

다익스트라 경로 찾기 알고리즘 장소와 거리가 주어진 트리에서 최단경로를 찾는 알고리즘.

 

처음엔 개념이 잘 이해안되서 다른 사람들이 코딩해놓은거 보다가 더 맨붕.

나중에 다시 볼때 읽기 쉽도록 dict형태 자료형으로 구현함.

 

기본적인 해결순서는 크게 전체 지도 roadMap과 방문정보, 소요거리정보, 이전place정보가 담겨있는 fastWay를 만듬

1.모든 place까지 가는 거리는 9999999(임의의 큰수)로 세팅 (집 -> 미용실 -> ?, 미용실 넘어 지도를 우리 눈으로 확인할 수 있지만 프로그램은 하나씩 탐색해봐야하기 때문에 무한하다고 가정하는것)

2.시작점에 나와있는 정보로 하나씩 방문하여 소요되는 거리를 기록, 시작점은(visit) 방문처리, 소요거리(lenth) 0처리

3.fastWay를 스캔하여(def fintNext) 방문하지 않은 곳(visit==0)중에 최단경로로 새로운 탐색을 시작(def markingPath)

4.반복

5.최종경로는 input받은 목적지를 통하여 역 추적하는 방식으로 구현 참조 : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=85293

 

할일 - 코딩테스트 끝나면 설명 수정하고 그동안 알고리즘 문제 푼것 정리하기.