다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

• 출발 노드와 그외 노드 간의 최단 거리를 구하는 알고리즘
• 에지는 항상 양수여야 한다는 제약 조건이 있다.

• 다익스트라 알고리즘의 핵심 이론

1. 인접 리스트로 그래프 구현하기

   1 → (2, 8), (3, 3)

   2 → (4, 4), (5, 15)

   3 → (4, 13)

   4 → (5, 2)

   5

2. 최단 거리 배열 초기화 하기

최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 적당히 큰 값 (999 같은) 값으로 초기화하기

1. 값이 가장 작은 노드 고르기

최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다.

예를 들어 위와 같은 경우는 1부터 시작하면 된다.