백준을 풀다보면 마주하는 최단 경로 탐색 알고리즘 다익스트라이다. 다이나믹 프로그래밍을 활용한 알고리즘으로 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때 음의 간선을 포함하면 안된다. 간선에 음수가 포함 되어있을 때에는 벨만-포드 알고리즘을 사용해야하는데 이것은 나중에 다루어 보고 일단 다익스트라에 대해서 살펴보자. 핵심은 1. 목표 정점까지의 최단 거리는 여러개의 최단 거리로 이루어져있다. 2. 그래서 하나의 최단 거리를 구할 때 그 전까지 최단거리를 이용해준다. 먼저 선언해주어야 하는 것이 우선순위 큐, 각 정점까지의 거리를 담을 dst[] 배열이다. 우선순위 큐는 다음 정점의 번호와, 다음 정점까지 거리를 담고 있고 다음 정점까지 거리를 최소로 하는 것이 루트로 갈 수 ..
