[알고리즘] 탐욕법 - 다익스트라 알고리즘 (Greedy Approach - Dijkstra's Algorithm)
다익스트라 알고리즘은 단일 출발점에서의 최단 경로의 문제를 푸는 알고리즘입니다. 앞선 DP 알고리즘에서 Floyd's Algorithm을 이용해서 모든 출발점에서의 최단 경로의 문제를 풀었습니다. 하지만 하나의 특정 vertex에서 다른 모든 vertex로 가는 최단 경로만 알고 싶다면 프로이드의 알고리즘은 너무 과합니다. 시작하기에 앞서 프로이드의 알고리즘은 n^3인 것에 반해, 다익스트라 알고리즘은 n^2입니다. 다익스트라 알고리즘은 Prim's Algorithm과 매우 흡사합니다. 집합 Y를 최단 경로를 구하려고 하는 vertex만 포함한다. (v_1이라고 함) 그리고 F는 공집합으로 초기화한다. v_1과 가장 가까운 vertex를 찾아서, 이 vertex를 Y에 포함하고, edge를 F에 포함한다..
