[파이썬 알고리즘 인터뷰] 13장 - 최단 경로 문제

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

• 최단 경로 문제
  • 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제
• 그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재
• 가장 유명한 것이 다익스트라 알고리즘
• 다익스트라 알고리즘
  • 항상 노드 주변의 최단 경로만 택하는 대표적인 그리디 알고리즘
  • 단순하고 실행 속도가 빠름
  • 노드 주변을 탐색할 때 BFS를 이용
• 다익스트라 알고리즘 특징
  • 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단 거리 계산이 끝났다고 가정
    - 즉, 탐색을 위한 출발노드가 갖는 최단거리는 최단거리임이 보장되어야함
  • 따라서, 음수를 처리할 수 없음
    - 벨만-포드 알고리즘과 같이 음수 사용이 가능한 알고리즘 사용
• 다익스트라 알고리즘 속도
  • BFS에서 가장 가까운 순서를 찾을 때 우선순위 큐 사용
  • 시간 복잡도가 O((V+E)logV)
    - 출발 노드부터 각 정점에 이어진 간선들 중 최소 가중치의 정점을 선택
    - 모든 간선이 heap에 push : E log E
    - 탐색할 노드 선택을 위해 heap에서 pop : V log E -> 다음 최소값과 힙의 특성 유지를 위해 구조를 바꿈
    - 따라서 이 둘을 더하면 (V+E) log E
    - 모든 정점이 출발지에서 도달이 가능하면 O(E logV)
  • 그런데 왜 log E가 아니고 log V인가?
    - 실제 구현해보면 우선순위 큐에 push되는 요소는 간선임
    - 그렇다면 힙 트리에 구성되는 요소의 개수인 E를 기준으로 log E, 즉, (V+E) log E라고 해야하지 않나?
    - 찾아보니 E <= V²이므로 E = V로 보며, log V라고 표시한다고 함(음...)
    - 다른 이유가 있을 수 있으니 계속 찾아보자