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

soooooyeon·2021년 5월 5일
0

다익스트라(Dijkstra) 알고리즘과 시간 복잡도

  • 하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘
  • 다익스트라 알고리즘은 다음에 방문할 정점을 선택하는 방법에 따라 크게 두가지로 구현이 가능하다.
    • 출발지로부터 모든 정점까지의 거리를 담는 우선순위 큐를 구현해, 출발점으로부터 거리가 가장 작은것부터 꺼내오기
      • 시간 복잡도 : O(E(log(V)))
        • (모든 간선을 검사하는 시간 복잡도) = E
        • (우선 순위큐에 넣고 빼는 과정의 시간 복잡도) = ElogE = ElogV
          (최악의 경우, 모든 간선을 검사할 때마다, 우선 순위큐에 넣어주어야 함)
    • 출발지로부터의 모든 정점까지의 거리를 나타내는 리스트를 선언하고, for문을 돌려, 그 중 거리가 가장 작은 것부터 꺼내오기
      • 시간 복잡도 : O(E + V^2)
        • (모든 간선을 검사하는 시간 복잡도) = E
        • (리스트에서 최단 거리 정점을 찾는 시간 복잡도) = V^2
profile
Junior iOS developer

0개의 댓글