최단 경로 알고리즘 그래프 G = (V, E)가 주어지고 여기서 E는 가중치를 가진 유향 간선들의 집합이다. 임의의 경로는 연속된 간선들로 구성된다. 경로를 구성하는 간선들의 가중치의 합이 해당 경로의 길이가 된다. 다익스트라 알고리즘은 음의 가중치가 없는 경우에 사용이 가능하다. 다익스트라 알고리즘이란? 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 그리디를 이용한 알고리즘으로 Prim이랑 유사한 방법이라고 보면된다. 구현하기 Dijkstar(s, A, d) s : 시작 정점 A : 인접 행렬 D : 시작 정점에서의 거리 정점의 집합