[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘 (Dijkstra Algorithm)

개념

- 특정한 한 정점(=노드)에서 출발하여 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘

- BFS와 DP를 활용한 최단경로 탐색 알고리즘

- DP를 활용하는 이유는 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 활용하기 때문

- 그래프의 간선마다 가중치가 존재할 때 사용 (음의 가중치는 존재하지 않음)

 

구현

- 최단 거리 테이블 MAX 값으로 초기화 (최단 거리를 저장해야 하므로 큰 수로 초기화 시킴)

- 출발 노드 설정

- 방문하지 않은 노드 중에서 최단 거리(가중치)가 가장 짧은 노드 선택

- 해당 노드를 거쳐 다른 노드로 이동하는 비용을 계산하여 최단 거리 테이블 갱신

- 계속해서 가중치가 가장 짧은 노드를 선택하면서 최단 거리 테이블 갱신

- 현재 노드로의 최단거리가 현재 가중치보다 작다면 update할 이유가 없으므로 continue ⭐️ (이 한 줄로 심화문제 풀 때, 시간초과 해결 가능..)

if(min[now.end] < now.weight) continue;

- 매번 최단 거리 테이블을 모든 원소를 탐색하는 방법이 있지만, 우선순위 큐를 사용하면 단순 탐색보다 시간 복잡도를 줄일 수 있음

 

코드

가장 기본적인 다익스트라 코드로 해결할 수 있는 백준 1753번 문제이다.

1753번: 최단경로

이 문제에 대한 풀이는 아래 포스팅한 글에 자세히 작성해두었다.

[백준] 1753번 최단경로 (JAVA)