[TAVE/파이썬 알고리즘 인터뷰] Ch13 | 최단 경로 문제 - 개념 정리

참고자료: 파이썬 알고리즘 인터뷰

최단 경로 문제

📌최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제다.

• 정점: 교차로
• 간선: 길
• 가중치: 거리나 시간과 같은 이동 비용

👉🏻그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다.

다익스트라 알고리즘

📌최단 경로 알고리즘 중 가장 유명하다. 네덜란드의 유명한 컴퓨터과학자 에츠허르 다익스트라가 대학원생 여자친구와 카페에 가서 20분 만에 고안한 알고리즘이다. 단순한 알고리즘이 가장 훌륭한 알고리즘이라는 것을 증명하는 대표적인 알고리즘이다.

 

1️⃣그리디 알고리즘

👉🏻구현하기 쉽지만 느리게 동작한다.

👉🏻다익스트라의 최초 구현에서는 시간 복잡도가 O(V제곱)였다. 왜냐하면 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 노드의 개수만큼 순차탐색을 수행하기 때문이다.

 

2️⃣BFS 구현

👉🏻우선순위 큐에 계속해서 노드와 거리에 대한 정보가 있는 원소를 거리순으로 정렬해서 넣는다. 처리한 노드는 무시하고 처리하지 않은 노드에 대해서만 탐색한다.

👉🏻미로에 들어갔을 때 BFS는 여러 사람이 실뭉치를 가지고 각각 새로운 길을 탐색하는 것이다. 여기서 다익스트라 알고리즘은 먼저 도착한 사람의 실뭉치를 사용한다. 하지만 가중치가 음수인 경우는 처리할 수 없다.

👉🏻BFS를 사용해 가장 가까운 순서을 찾을 때 O((V + E)log V)이고, 모든 정점이 출발지에서 도달이 가능하면 O(E log V)가 된다.