[그래프] 다익스트라

---

⌨️ 다익스트라

특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하여 문제 해결 가능

 

기능	특징	시간 복잡도(노드 수: V, 에지 수 :E)
출발 노드와 모든 노드 간의 최단거리 탐색	에지는 모두 양수	O(ElogV)

 

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

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

 

그림 자리

 

 

다익스트라 알고리즘은 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 더욱 좋다.

그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결

 

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

최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 Integer.MAX_VALUE 등 충분히 큰 값으로 초기화

 

그림 자리

 

 

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

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

 

그림 자리

 

 

1.4. 최단 거리 배열 업데이트하기

선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트.

1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트.

연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트

 

최단 거리 업데이트 방법
Min(선택 노드의 최단 거리 배열의 값+ 에지 가중치, 연결 노드의 최단 거리 배열의 값)

1.5. 과정 3~4를 반복해 최단 거리 배열 완성하기

모든 노드가 처리될 때 까지 과정 3~4를 반복

과정 4에서 선택 노드가 반복되지 않도록 방문 배열을 만들어 처리하는 식의 방식 선택

 

 

✔ 마무리 정리
1. 출발 노드와 그 외 노드간의 최단 거리를 구하는 알고리즘
2. 에지는 항상 양수여야 한다는 제약조건 
3. ⭐출발 노드와 도착 노드만의 최단 거리가 아닌 모든 노드와의 최단 거리가 배열로 완성됨을 기억

 

 

2. 문제 선정

https://www.acmicpc.net/problem/1753

1753번: 최단경로

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

https://www.acmicpc.net/problem/1854

1854번: K번째 최단경로 찾기