[백준1753&파이썬] 다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단거리를 구할 수 있다.

# 문제

백준 1753 최단경로 파이썬 풀이

1753번: 최단경로

# 코드

'''
  1. 다익스트라는 시작정점으로부터 모든 정점까지의 최단거리를 구할 수 있다
  2. 간선(Edge)의 값이 0 이상의 양수일때 정상 작동한다.
  - 최단 거리 테이블 초기화( 시작 노드 0, 나머지 inf )

  - https://www.acmicpc.net/board/view/82405 그래프 초기화 관련
  - 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
  - 방문처리에 관해서 생각해본다.
  - heap이 우선순위로 정렬하게 되는 타겟 ( weight, vertex)이면 weight다
  - 왜 다익스트라가 성립이 되는지 생각해보기

'''
import heapq
import sys
from collections import defaultdict

V,E = map(int, sys.stdin.readline().split())
start_vertex = int(sys.stdin.readline())
graph = defaultdict(list) # defaultdict 때문에 틀리는 문제 발생

distance = [float("inf")] * (V+1) # 거리 업데이트 배열
distance[start_vertex] = 0
heap = list()
heapq.heappush(heap,(0, start_vertex)) # 힙에 시작노드 넣어주기

#  u -> v , weight
for _ in range(E) :
  # 그래프 구성하기
  u,v,w = map(int,sys.stdin.readline().split())
  graph[u].append((v,w))

while len(heap) != 0 :
  cur = heapq.heappop(heap) # ( weight, vertex)
  # print(distance, cur)

  if distance[cur[1]] < cur[0] :
    continue # 큐에서 뽑아낸 값과 갱신된 거리 비교, 방문처리가 된 곳임.

  for neighbor in graph[cur[1]] :
    cost = distance[cur[1]] + neighbor[1]
    # print(f"cost : {cost}")
    if cost < distance[neighbor[0]] :
      distance[neighbor[0]] = cost
      heapq.heappush(heap, (cost , neighbor[0]))


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

 

# 풀이

## 다익스트라 

• 다익스트라는 한정점에서부터 연결된 모든 정점까지의 최단거리를 구할 수 있다
• 간선(Edge)은 음의 아닌 실수, 즉 [0, inf)을 가질 수 있다.
• heap을 사용하여 다음번에 방문해야하는 노드를 빠르게(효율적이게) 관리할  수 있다.
• 다익스트라를 구성하기 위해서는, graph, distance(시작 정점으로부터 target정점까지의 weight를 최신화), heap(노드를 확정시키고, 다음번에 방문할 곳을 정하기 위해서) 필요하다.
• 방문처리를 방문배열( visit )를 따로 만들지 않고 아래 코드처럼 할 수 있다.

if distance[cur[1]] < cur[0] :
  continue # 큐에서 뽑아낸 값과 갱신된 거리 비교, 방문처리가 된 곳임.

 

 

## 문제 풀때 주의해야하는 상황

• 서로 다른 두 정점 사이에 여러개의 간선이 존재 할 수 있다. 그렇기 때문에, graph를 아래와 같이 초기화하면 여러개의 간선을 저장할 수 없고, 하나의 간선만이 저장 된다.

graph = defaultdict(defaultdict) # 이렇게 사용하면 안됨
graph = defaultdict(list) # 이렇게 사용해야 함

 

## heapq은 첫번째 매개변수를 기준으로 최소힙을 구성한다.

heapq.heappush(heap,(0, start_vertex)) # 힙에 시작노드 넣어주기
cur = heapq.heappop(heap) # ( weight, vertex)