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

다익스트라 알고리즘은 그래프의 시작점에서 모든 노드까지의 최단 경로를 찾는 알고리즘입니다.

 

알고리즘 아이디어

다익스트라의 알고리즘의 아이디어는 '최단거리는 최단거리들의 합으로 이루어져있다.'

라는 그리디(Greedy)한 생각에서 출발합니다.

 

동작 과정

- 방문하지 않은 점들 중 값이 가장 작은 점을 방문한다.

- 방문한 점을 통해서 갈 수 있는 점들 중, 아직 방문하지 않은 점의 값이 이전에 기록한 값보다 작을 시(거리가 더 짧을 시), 거리를 갱신한다.

 

주의 사항.

다익스트라는 모든 가중치(값)가 음수가 아닐 경우에만 사용할 수 있습니다.

 

 

 

---

예시) 1번 노드에서 갈 수 있는 모든 점에 대해 최단거리 구하기

 

시작점 = 1번 노드

 

1. 초기화

1.1 초기 시작점(1번 노드)을 0으로 초기화.

1.2 나머지 점들을 무한대로 초기화. → 아직 각 점들에 대한 거리를 모르기 때문에.

 

2. 아직 방문하지 않은 곳 && 가능한 비용이 작은 곳. 

 

2.1 1번 노드에서 갈 수 있는 모든 노드를 간다. (5, 9, 1로 갱신)

 

2.2 다음 선택은 5번 노드(점)이다. 왜냐하면 거리가 1로 후보(5, 9, 1) 중 가장 작은 값이다.

 

2.3 비용 비교

 - 결과 : 4번 노드에 저장된 비용 9를 3으로 바꾼다.

 - 이유 : 1번 노드 → 4번 노드(비용 : 9) < 1번 노드 → 5번 노드 → 4번 노드 (비용 : 3)

 

 

3. 방문하지 않은 곳에 대해 반복

 

4. 최종 결과

 

---

특징

- 시작점을 고정시킨 후, 모든 노드들에 대해 최단 경로를 찾는다.

- 방문한 곳에 대해 거리가 최종 확정된다.

 

구현 

1. 배열을 이용하는 경우

    - 시간복잡도 : O(V^2)

 

2. 우선순위 큐를 이용하는 경우

    - 시간복잡도 : O(ElogV)

 

---

참고하면 좋은 블로그들

https://jason9319.tistory.com/307

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

https://alswnsdl.tistory.com/12

다익스트라 알고리즘(Dijkstra's algorithm) 개념

 

https://travelbeeee.tistory.com/424

[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra)