Skip to content

Latest commit

 

History

History
35 lines (23 loc) · 886 Bytes

shortest-path.md

File metadata and controls

35 lines (23 loc) · 886 Bytes

최단 경로

최단 경로(Shortest Path)는 한 정점에서 다른 정점까지의 최소 비용을 구하는 문제입니다.

먼저 구분할 것

  • 간선 가중치가 없는가
  • 가중치가 모두 같은가
  • 음수 간선이 있는가

자주 쓰는 선택

  • 가중치 없음: BFS
  • 가중치 양수: 다익스트라(Dijkstra)
  • 음수 간선 가능: 벨만-포드(Bellman-Ford) 계열

파이썬 구현 포인트

import heapq

dist = [INF] * (n + 1)  # -> 최단 거리
dist[start] = 0
pq = [(0, start)]  # -> (거리, 정점)

실수하기 쉬운 것

  • BFS로 풀어야 할 문제에 다익스트라를 쓰는 것
  • 음수 간선이 있는데 다익스트라를 쓰는 것
  • 이미 더 짧은 거리로 방문한 정점을 다시 처리하는 것

기억할 문장

  • 최단 경로는 먼저 "간선 가중치가 어떤가"부터 본다.