🚀 What I Will Learn

• 다익스트라(Dijkstra)의 최단 경로에 대해 이해하기

다익스트라(Dijkstra)의 최단 경로란? 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘

---

다익스트라(Dijkstra)의 최단 경로

1️⃣ 다익스트라(Dijkstra)의 최단 경로란?

• 다익스트라의 최단 경로(Dijkstra‘s Shortest Path Algorithm)는 매우 잘 알려진 알고리즘
• 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로
• 동작 원리가 프림 알고리즘과 흡사
• 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 적합한 알고리즘이다

---

2️⃣ 다익스트라의 최단 경로의 원리

1) 그래프의 시작점을 선택하여 트리 T에 포함시킨다
2) T에 포함된 노드와 T에 포함되지 않은 노드 사이의 간선 중에서 이동 거리가 가장 작은 간선을 찾는다
3) 해당 간선에 연결된 T에 포함되지 않은 노드를 트리 T에 포함시킨다
4) 모든 노드가 포함될 때까지 2)와 3)의 과정을 반복한다

동작 원리가 프림 알고리즘과 흡사하다

✔️ 다익스트라의 동작 과정

1) 시작 노드인 1과 인접한 노드의 거리 정보를 테이블에 포함 ➡️ 노드 2, 3, 4에 대한 거리 정보 2, 5, 1

• 갈 수 없는 거리는 무한으로 설정

2) 시작 노드 1과 이동 거리가 가장 짧은 4를 시작으로 5와의 거리는 1이므로 1+1를 한 값인 2를 노드 5의 거리로 입력

3) 그 다음 이동 거리가 짧은 거리 2인 노드(2와 5중 하나)를 선택 ➡️ 2를 선택한다는 가정하에 2를 기준으로 거리를 갱신

4) 3)에서 선택한 2 다음인 5에서 시작 ➡️

• 5를 거쳐 3으로 가는 거리는 3이고,
• 5를 거쳐서 6으로 가는 거리는 4

5) 그 다음 경로가 짧은 3을 테이블에 추가 시키고, 그 다음인 6을 추가 시킴으로써 종료

다익스트라의 알고리즘은 각 간선에 대한 정보를 우선순위 큐에 담아 처리하는 방식으로 구현할 수 있다

---

✨ tl;dr

• 다익스트라의 최단 알고리즘은 프림 알고리즘과 동일하 𝑂(𝐸𝐿𝑜𝑔𝑉)의 시간 복잡도를 가진다

시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것을 의미