백준

1753번 최단경로 / python

문제

풀이과정

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로

다익스트라 최단 경로 알고리즘

그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

음의 간선이 없을 때 정상적으로 작동

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산, 최단 거리 테이블 갱신
5. 모든 노드를 방문할 때 까지 3, 4의 과정을 반복

시간 복잡도 O(ElogV)
현재 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 이용
거리가 짧은 원소가 우선순위 큐의 최상위 원소로 위치
해당 노드를 이미 처리한 적이 있다면 무시하고 아직 처리하지 않은 노드에 대해서만 처리

소스코드

#백준 1753번 최단 경로
#https://www.acmicpc.net/problem/1753

#주어진 시작점에서 다른 모든 정점으로의 최단 경로
#다익스트라 알고리즘 시간복잡도 O(ElogV)

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9) #경로가 존재하지 않는 경우, 무한, 10억

v, e = map(int, input().split()) #정점의 개수 v, 간선의 개수 e
k = int(input()) #시작점

graph = [[] for _ in range(v+1)] #각 노드에 연결된 노드에 대한 정보
distance = [INF] * (v+1) #최단 거리 테이블 무한으로 초기화

for i in range(e):
  start, end, weight = map(int, input().split()) #u에서 v로 가는 가중치 w
  graph[start].append((end, weight))

def dijkstra(start):
  q = [] #우선순위 큐
  heapq.heappush(q, (0, start)) #시작노드로 가는 최단 거리 0, 큐에 삽입
  distance[start] = 0 #시작 노드에서 시작 노드로 거리 0

  while q:
    dist, now = heapq.heappop(q) #가장 최단 거리가 짧은 노드 정보 큐에서 꺼내기

    if distance[now] < dist: #이미 처리된 노드까지 거리가 큐의 최단거리 보다 짧은 경우
      continue #처리된 노드 넘어간다

    for i in graph[now]: #현재 노드와 연결된 다른 인접 노드
      cost = dist + i[1] #현재 노드 거쳐 인접 노드로 가는 비용
      if cost < distance[i[0]]: #현재 노드를 거쳐가는 경우가 더 짧은 경우
        distance[i[0]] = cost #최단 거리 갱신
        heapq.heappush(q, (cost, i[0])) #갱신된 노드 정보(거리, 번호) 큐 삽입

dijkstra(k)

for i in range(1, v+1):
  if distance[i] == INF:
    print('INF')
  else:
    print(distance[i])