다익스트라

 

📍 정의 및 특징

가중치가 있는 그래프에서 출발 노드에서부터 모든 노드 간 최단 거리 탐색 알고리즘

특정 지점까지의 거리 = A까지의 거리 + A에서 특정 지점까지 소요되는 거리

- 제약조건 : 엣지, 항상 양수여야 한다.

- 시간 복잡도 : O(E log V)

(모든 지점 간 최단 거리 구하는 시간 복잡도 : O(V³))

 

+ 인접 리스트 쓰는 게 더 효율적

+ 꼭 우선순위 큐를 사용해야 함. (사용자 정의 정렬)

+ 가중치 있는 그래프 담기 위한 노드 클래스 별도 구현 필요 (또는 int[])

 

#가중치O    #양수    #모든정점간최단경로탐색

 

 

📍 필요 변수 · 자료구조

1.  인접 리스트

2.  최단 거리 배열

3.  우선순위 큐

4.  방문 배열 

5.  노드 클래스

 

 

 

📍 실행 과정

1. 인접 리스트로 그래프 구현     ⇨ (노드, 가중치) 형태
2. 최단 거리 배열 D 초기화         ⇨ 출발 노드 : 0 / 이외 노드 : INF
   
   
3. 최단 거리 배열에서 방문X & 최소값(=0) 가진 노드 선택
4. 최단 거리 배열 업데이트
       4-1) Min(선택 노드의 최단 거리 배열의 값 + 엣지 가중치, 연결 노드의 최단 거리 배열의 값)
           (예: D[1] + 8 < D[2] = 0 + 8 < ∞ ⇒ D[2]값을 8로 갱신)
       4-2) 업데이트 수행 시, 연결 노드를 우선순위 큐에 삽입
   
   
5. 모든 노드가 선택될 때까지 과정 반복 ⇨ 방문 배열 visited 만들어 중복 처리

 

 

➕ 예제

[백준/JAVA] 1753번: 최단경로

[백준/JAVA] 1916번: 최소비용 구하기

[백준/JAVA] 18352번: 특정 거리의 도시 찾기

 

[백준/JAVA] 1504번: 특정한 최단 경로

 

---

(참고)

Do it 알고리즘 코딩 테스트 자바편