[파이썬 알고리즘 인터뷰] 최단 경로 문제

• 최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제
  • 정점: 교차로, 간선: 길, 가중치: 거리 & 시간 등의 이동 비용
• 다익스트라 알고리즘: 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 -> BFS 이용
  • 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다

 

743. network delay time

- 다익스트라 알고리즘 -> 시작점에서 각 노드까지 최단시간 계산하고 저장(BFS) 및 계산되지 않는 노드 여부 확인

• heapq 모듈에는 우선순위 업데이트 기능 없음
• 이전 노드의 값이 무엇인지 필요없으므로 생략

787. cheapest flights within k stops

- 다익스트라 알고리즘 -> k번 경유 하는 것까지만 탐색하면서 종점에 다다르면 그때까지의 최소 가격 반환