어떤 도착지에 대해서 출발 노드가 여러개일 때
도착노드까지의 최단거리를 구해야 하는 상황을 해결해 봅시다.
(어떤 출발 노드에서 출발하더라도 상관없습니다.)
(간선의 비용은 모두 음이 아니며, 1을 초과할 수 있습니다.)
일반적으로는 다음의 전략을 생각해볼 수 있습니다 :
각 출발노드에서 도착노드까지 다익스트라를 모두 수행해, 각각의 최단거리를 모두 비교하는 방법입니다.
시간복잡도를 계산해보면
N: 출발 노드의 개수
V: 그래프의 노드 개수
E: 그래프의 간선 개수
라고 했을 때,
시간복잡도는 O(N E logV) 가 됩니다.
하지만 아주 간단한 처리로 O(ElogV) 에 목적을 이룰 수 있습니다.
다익스트라에서 최단거리에 저장되는 배열들의 정의는 다음과 같습니다
f[n]: 출발 노드에서 n번 노드까지의 최단거리
하지만 이를 다음과 같이 바꿀 수 있습니다.
f[n]: 모든 출발 노드를 고려했을 때, n번 노드까지의 최단거리
생각해봅시다.
다익스트라는 priority_queue를 사용하기 때문에 push 순서와 상관없이
항상 pop되는 요소가 queue에 존재하는 요소들중 가장 최단거리임을 보장할 수 있습니다.
즉 출발 노드를 처음에 여러개 넣어놓더라도 항상 최단거리인 노드부터 pop하기 때문에
단지, priority_queue에 출발지를 여러개 넣어놓고 다익스트라를 수행하는 것만으로도
여러 출발지를 고려한 최단거리를 구할 수 있습니다.
이 문제에서 해당 소재를 적용해 볼 수 있습니다.