[BAEKJOON] [1753] 최단경로: PYTHON

[1753] 최단경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성

1753번: 최단경로

Input

• 첫째 줄에 정점의 개수 V와 간선의 개수 E (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 
  : 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정
• 둘째 줄에는 시작 정점의 번호 K (1 ≤ K ≤ V)
• 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 
  : u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻
•  u와 v는 서로 다르며 w는 10 이하의 자연수
• 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음

Output

• 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
• 시작점 자신은 0으로 출력
• 경로가 존재하지 않는 경우에는 INF를 출력

 

✨ Solve

• 다익스트라 알고리즘을 사용해서 풀이

[Algorithm] 다익스트라(Dijkstra) 알고리즘: 최단경로 구하기

• python heapq 사용
• 최단거리 테이블

🔮 heapq
- 파이썬에서 우선순위 큐를 구현하는데 유용한 도구
- 최소 힙(min heap)을 지원하여 최소거리를 먼저 추출하는데 사용 할 수 있다.
- heappush(), heappop()
 - pop 메서드는 최소값을 반환: 최소 힙으로 사용 가능

 

💻 Code

# python 68356KB 676ms

import sys
import heapq

input = sys.stdin.readline # input 함수 새로 정의
INF = int(1e9) # 무한대 정의

V, E = map(int, input().split())

snode = int(input()) # 시작 정점

graph = [[] for _ in range(V+1)] # 노드의 개수만큼 이중 리스트 생성
distance = [INF] * (V+1) # 시작 정점에서 각 정점까지의 거리를 무한대로 설정

for _ in range(E):
  u, v, w = map(int, input().split())
  graph[u].append((v, w)) # 노드 u에서 v로 가는 가중치 w인 간선 정보
    
## 다익스트라 알고리즘 함수
def dijkstra(start):
  q = [] # 우선순위 큐 정의
  
  heapq.heappush(q, (0, start)) # 시작점의 거리, 노드 큐에 추가
  distance[start] = 0 # 시작 노드의 최단거리 거리 0

  while q: # q가 비어질 때까지 반복
    dist, now = heapq.heappop(q) # 큐에서 가장 가까운 거리, 노드번호 꺼냄

    # 최단거리테이블( distance[꺼낸 노드번호] ) 에 기록된 거리가 꺼낸 거리(dist)값 보다 작으면 이웃 노드 확인 할 필요 없음 
    # 처음에는 무한대와 비교하므로 무조건 첫번째는 아래의 if문을 통과함
    if distance[now] < dist:
      continue
      
    for i in graph[now]: # 이웃 노드 확인, 이웃 노드 까지의 거리 체크
      # i[0]: 현재 노드에서 갈 수 있는 노드 번호
      # i[1]: 현재 노드에서 위의 노드 까지의 거리
      
      # i[0] 까지의 최소 거리
      cost = dist + i[1] 

      # cost 값이 최단 거리 테이블 거리 정보보다 작으면 값 갱신
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0])) # 큐에 해당 노드까지의 최단거리, 노드번호 추가

dijkstra(snode)

## 결과물 출력
for i in range(1, V+1):
  if distance[i] == INF:
    print("INF")
  else:
    print(distance[i])

 

🎯 Question

1. 다익스트라 알고리즘은 왜 음수의 간선은 계산 할 수 없지?