최단 경로 (다익스트라) 최단 경로를 찾는 문제는, 한 정점으로부터 다른 모든 정점으로 가는데 걸리는 최단 경로를 통해 결국은 원하는 지점으로 최단경로를 찾는 방법이다. 다익스트라는 여기서 첫 점을 기준으로 정점들을 추가하며 거리를 갱신시킨다. D(z)를 x에서 z까지의 최단 경로라 한다면 $D(z) = Min(D(z) , D(y) + c(y,z))$ 의 식을 계속 진행하여 전체 경로에 대한 최단 경로를 알아낸다. //최단 경로 수도 코드 //입력 : 가중치 그래프 G //출력 : distance 배열, distance[u]는 v에서 u까지의 최단 거리 shortest_path(G,v) S = v; for(G의 각 정점 w) do distance[w] = weight[v][w]; while 모든 정점이 ..