[알고리즘] 최단경로 1753 python

문제 바로가기

---

풀이

최단경로 문제와 같이 간선의 길이까지 생각해야하는 문제는 보통 DFS로 풉니다.
DFS 중에서도 최단경로 문제는 Dijkstra 알고리즘을 사용하는 경우가 많습니다.

우리가 v라는 노드로 가고싶다면

• u를 경유해서 v를 가는 거리
• 바로 v를 가는 거리
  를 비교해서 짧은 것으로 저장해나갑니다.

노드 간 최단거리를 수정하는 방법

첫번째 방법

• node0에서 갈 수 있는 간선들에 대해서 업데이트
• node0에서 갈 수 있는 간선들을 경유해서 가는 거리와 node1에서 바로 갈 수 있는 간선들을 비교하고업데이트
• n번째 노드까지 진행

두번째 방법

• priority queue에 시작 노드 삽입
• 시작 노드에서 갈 수 있는 간선들을 업데이트
• 시작 노드에서 갈 수 있는 간선들을 priority queue에 넣기
• priority queue에서 가장 짧은 거리를 가진 간선을 pop해서 동일하게 수행
• queue가 빌 때까지 진행

import sys
import heapq


V, E = map(int, sys.stdin.readline().split())
K = int(input())

graph = [[] for _ in range(V+1)]
dist = [float('inf')] * (V+1)
dist[K] = 0

for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append((v, w))

pq = []
heapq.heappush(pq, (0, K))

while(pq):
    curDist, curNode = heapq.heappop(pq)
    if dist[curNode] < curDist:
        continue
    for destNode, destDist in graph[curNode]:
        d = curDist + destDist
        if dist[destNode] > d:
            dist[destNode] = d
            heapq.heappush(pq, (d, destNode))

for i in range(V+1):
    if i == 0:
        continue
    if dist[i] == float('inf'):
        print("INF")
    else:
        print(dist[i])