최단경로

가. 무엇인가 a. 최단경로 - 시작정점부터 모든 정점으로 가는 최단경로를 구하는 알고리즘 => 가중치가 양수일 경우에만 사용가능 - 진행 0. 모든 정점이 가지고 있는 가중치합(시작정점부터 도착정점까지의 최단경로)을 INF(엄청큰값) 초기화한다. 1. 현재 정점(동그리미)이 가진 간선들중 가장 최소값을 가지는 간선의 정점을 방문한다. => 이때 방문 정점이 가지고 있는 가중치합은 여러 정점을 거쳐왔을수도 있다. 2. 현재 경로의 가중치합과 방문정점이 가지고 있는 가중치의 합을 비교해서 최소값으로 업데이트한다. 3. 현재 시점에서 가중치합이 더 작았다면 방문정점에서 다시 1번을 수행한다. 나. 구현하기 a. 배열 public class 다익스트라 { public static void main(String..