최단경로 : 다익스트라 : dijkstra : 방향가중치그래프

유형은 DP+그리디 가 합쳐진 느낌이다

 

A노드에서 B노드로 간다는 방향이 있는 그래프에서 사용한다. 근데 그렇게 이동하는데 비용이 각각 다르다. 다익스트라는가중치가 음수인 경우에는 사용할 수 없다.

 

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

이 자료들로 공부했다

 

가장 거리가 짧은 노드부터 탐색하는 이유

while q: # 큐가 비어있지 않다면
    # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heappop(q)

이 부분이다.

간단하게 a->c가 최단경로이려면 a->b도 최단경로여야 하기 때문

 

위에서 이렇게 뽑았기 때문에

 if distance[now] < dist:
    continue

visited를 사용하지 않고 이미 방문했는지 확인하는 방법으로 위의 코드를 사용할 수 있다.

지금 들어온 dist값보다 더 작은 경우가 있었다는 것은 이미 방문했다는 의미이다.

 

 

부등호에 왜 =을 넣으면 안 될까 ( if distance[now <= dist )

0<=0 이면 while을 돌지 않고 끝나버린다

이미 큐에 넣을 때 distance에 업데이트를 하기 때문에

다음 반복 때 돌면 무조건 continue에 걸려서 진행이 되지 않는다.

 

 

Tip

heapq는 맨 처음 수를 기준으로 정렬되기 때문에 dist를 튜플의 가장 첫 번째에 넣어주면 정렬된다.