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

다익스트라 (Dijkstra Algorithm)

다이나믹 프로그래밍을 이용한 꼭짓점간의 최단 경로를 찾는 알고리즘

(start_node -> end_node

start_node -> all_node)

특징

• 너비우선탐색(BFS)를 기본적으로 한다.
• 가중치 그래프에서 간선의 가중치 합이 최소가 되도록하는 알고리즘

효율성

• 일반 큐 사용시 O(E+V^2), 우선순위 큐 사용시 O(ElogV)

장점

• 실행 속도가 빠르다.
• 그래프가 큰 경우에도 사용 가능하다.

단점

• 음의 가중치가 포함되어 있다면 사용할 수 없다.
• 최장 거리를 구하는 데에는 다익스트라 알고리즘을 사용할 수 없다.

우선순위 큐를 사용해 다익스트라 알고리즘 구현

MinHeap방식을 사용한 우선순위 큐 사용

① 초기화

• 첫 정점을 기준으로 배열을 선언하여 첫 정점부터 각 정점까지의 거리 저장
  • 초기에는 첫 정점의 거리를 0으로, 나머지는 inf로 저장
  • 우선순위 큐에는 첫 정점(A,0) 삽입

② 최초 (A,0)로부터 인접한 노드와의 거리 계산

• 첫 정점으로부터 인접한 노드들에 대한 거리를 배열에 업데이트
• 업데이트 된 노드를 우선순위 큐에 삽입

③ 이후 우선순위 큐에서 하나씩 노드를 추출하며 ② 반복

• 우선순이 큐에서 노드를 추출해 하나씩 처리
  • 꺼낸 노드로부터 인접한 노드들에 대한 거리를 합산하여 배열 업데이트
    • 기존 배열에 입력된 것보다 작은 경우에는 업데이트
  • 이후 배열에 업데이트된 노드들만 다시 큐에 삽입
    • 큐가 우선순위 큐이므로 거리가 가까운 순서대로 삽입됨