코딩배우는고양이

다익스트라 알고리즘 단일 시작점 최단 경로 알고리즘으로 하나의 정점에서 출발하였을 때 다른 모든 정점으로의 최단 경로를 구한다. 1을 기준으로 잡고 최단 경로를 구한다고 할 때, 4의 경우 1 -> 4로 가는 비용보다 1 -> 3 -> 4로 가는 비용이 더 적기 때문에 더 적은 비용을 갱신할 수 있다. 구현 방법 BFS와 유사한 형태로, 시작점에서 가까운 순서대로 정점을 방문한다. 가중치가 있는 그래프에서는 BFS를 그대로 적용하기 어렵기 때문에 우선순위큐를 사용하여 해결한다. 각 정점까지의 최단 거리를 저장하는 배열 dp[]를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사한다. 간선 (u, v)를 검사한다고하면 u까지의 최단 거리에 (u, v)의 가중치를 더해 v까지의 경로의 길이를 찾는다...