다익스트라 알고리즘은 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구하는 알고리즘이었다.
모든 정점에서 특정 도착점까지의 최단거리는 어떻게 구할 수 있을까?
1. 각 정점에 대해 다익스트라 알고리즘 적용하기
이러한 접근법을 사용하면 의 시간복잡도로 구현할 수 있다.
그렇지만 반대로 생각해보자
2. 간선을 뒤집어 특정 도착점에서 다른 정점까지의 최단 거리로 생각하기
반대로 특정 도착점에서 다른 정점까지의 최단거리로 생각하면 다익스트라 알고리즘 한 번으로 시간복잡도 안에 구현할 수 있습니다.
