다익스트라 알고리즘

인트로

• 네덜란드의 컴퓨터과학자 다익스트라가 발명한 알고리즘
• 특정 정점에서 나머지 정점으로의 최단 경로를 구하는 알고리즘
• 가중치가 모두 양수일 때만 사용 가능하다.

원리

1. 출발노드 설정
2. 출발노드 기준으로 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용 갱신
5. 3~4번을 반복

예시를 들어보자. 출발노드 : 1

• 1 → 3의 비용은 5

• 그런데 1 → 2 → 3의 비용이 2 + 1 = 3이라면?

  배열을 다음과 같이 바꾼다.

실제 코딩

• 특정 정점에서 가중치가 가장 작은 정점을 선택해야 한다.
• 따라서 우선순위 큐를 사용한다.
• 이때의 시간복잡도는 O(E \cdot logV) 이다.

다익스트라 알고리즘은 특정 정점에서 인접한 정점을 가중치가 작은 순으로 큐에 저장해가며 거리가 짧은 경로를 먼저 추출한다.

코드