다중 출처 다익스트라 (Multi-Source Dijkstra)

그래프 탐색 문제를 풀다 보면 "여러 개의 출발점 중 어느 곳에서 출발하든 상관없이 가장 가까운 목적지까지의 최단 거리를 구하라"는 조건을 만날 때가 있습니다.이때 출발점마다 다익스트라 알고리즘을 매번 실행하면 반드시 시간 초과가 발생합니다. 이를 해결하는 핵심 기법이 바로 다중 출처 다익스트라(Multi-Source Dijkstra)입니다.1. 일반 다익스트라 vs 다중 출처 다익스트라구분일반 다익스트라 (Single-Source)다중 출처 다익스트라 (Multi-Source)출발점단 1개의 시작 노드여러 개의 시작 노드 그룹탐색 목적특정 출발점에서 다른 노드들까지의 최단 거리가장 가까운 출발점 기준으로 다른 노드까지의 최단 거리PQ 초기화시작 노드 1개만 dist = 0 설정 후 PQ 삽입모든 시작 ..