Graph(4): Single Source Shortest Path

최단 경로 문제에서 BFS 를 사용하지만, BFS는 무가중치 그래프에서만 문제를 해결 가능하다. 가중치 그래프에서 최단 경로를 찾아야한다면 어떻게 해야 할까? Single Source Shortest Path 알고리즘을 사용하면 된다. 두 가지 구현이 있다.

다익스트라 알고리즘

(* 음수가 아닌 가중치 그래프에서 "단일 소스 최단 경로" 문제를 해결 가능하다.)

시작점을 중심으로 다른 정점에 도달하기 위한 "최단 경로"를 업데이트하면서 바깥쪽으로 확장한다.

• 시간 복잡도: O(E + V*logV)
• 공간 복잡도: O(V)

벨만-포드 알고리즘

음수 포함한 가중치 그래프에서 "단일 소스 최단 경로" 문제를 해결 가능하다.(하지만 사이클은 없어야 한다.)

• 시간 복잡도: O(V * E)
• 공간 복잡도: O(V)