다익스트라 최단경로

최단 경로

• 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다.
• 최단 경로 문제는 여러 방식 또는 여러 상황에서 나온다.
• 그래프에서 각 지점을 노드라고 통친한다.
• 지점을 연결시키는 선(도로)을 그래프에서 간선이라고 한다.

다익스트라 최단 경로 알고리즘 개요

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 작동한다.
• 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류 된다.

다익스트라 최단 경로 알고리즘

알고리즘의 동작 과정]

 

다익스트라 알고리즘:동작 과정 살펴보기

 

다익스트라 알고리즘:개선된 구현 방법 성능 분석

• 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이다.
• 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V이상의 횟수로는 처리되지 않습니다.
• 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.

출처]

다익스트라 최단경로: 다익스트라 알고리즘 - 나무위키 (namu.wiki)