선행지식

• Graph
• Priority Queue

기본 개념

다익스트라 알고리즘은 시작 정점 하나가 주어졌을 때, 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

가중치가 음수가 아닌 그래프에서 사용할 수 있으며, 매 단계에서 현재까지 최단 거리가 가장 작은 정점을 확정하는 방식으로 동작한다.

예시 워크스루

예시 그래프는 정점 1에서 시작한다.

• 간선 가중치: 1→2(2), 1→3(5), 2→3(1), 2→4(2), 3→4(3), 3→5(1), 4→5(2)

초기화

• 거리 배열: [0, INF, INF, INF, INF]
• 우선순위 큐: (0, 1)

정점 1 확정 후 완화

• 2의 거리: 2
• 3의 거리: 5
• 거리 배열: [0, 2, 5, INF, INF]

정점 2 확정 후 완화