Dijkstra

최단 경로 찾기 (Shortest path problem) 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제 다익스트라 (Dijkstra) 알고리즘 주어진 출발점에서 시작 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 Pseudo code ShortestPath(G, s) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 출발점 s로부터 (n - 1)개의 점까지 각각 최단 거리를 저장한 배열 D 1. 배열 D를 ∞로 초기화시킨다. 단, D[s] = 0으로 초기화한다. // 배열 D[v]에는 출발점 s로부터 점 v까지의 거리가 저장된다. 2. whi..