Dijkstra's Algorithm   다익스트라 알고리즘, 데이크스트라 알고리즘

(2022-11-08)

Dijkstra 알고리즘, 벨만 포드 알고리즘


1. 최단 경로 알고리즘 (Shortest Path Algorithm)그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘들을 총칭
     - 특히, 그래프방향성이고, 가중치를 갖으며, 순환을 포함하는 경우

  ㅇ 여기서는, 단일 출발지 최단경로 문제 (single source shortest paths problem)에 국한 함
     - 단일 출발지로부터, 임의 다른 모든 정점까지, 모든 최단 경로를 찾는 탐색 알고리즘
        . 하나의 출발 정점에서 임의 다른 모든 정점에 대한 최단 경로를 찾는 문제
        . 결국, 총 n개 정점에서, 시작 정점으로부터 (n-1)개의 최단 경로를 구하는 문제
     - 단일쌍 최단 경로 (single pair shortest path) 문제 라고도 함

  ㅇ 例) 다익스트라 알고리즘, 벨만 포드 알고리즘 등
     - 단일 출발지 최단 경로 계산 알고리즘
        . 단일 출발 정점에서 출발하여, 나머지 모든 정점까지의 최단 경로를 찾아냄


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

  ㅇ Dijkstra가 1956년에 개발하고, 1959년에 발표
     - Edsger W. Dijkstra (1930~2002) : 네덜란드 과학자

  ㅇ 그래프 상의 특징
     - 간선에서 음의 가중치를 허용 않음
     - 순환 포함 허용
     - 기본적으로, 탐욕 알고리즘에 속함
        . 매번 가장 비용이 적은 노드를 선택하려고 함

  ㅇ 방식 상의 특징
     - 첫 출발 정점을 기준으로 함
     - 연이어, 연결된 정점들을 추가해가며, 최단 거리를 갱신해 감
     - 항상, 각 노드에 대해, 현재까지의 최단 거리 정보최단 경로 테이블(1차원 리스트)에 저장,
     - 이 최단 경로 테이블을 계속 갱신해 나감
     - 결국, 시작 정점에서 모든 다른 정점까지의 최단 경로들은, 신장 트리를 형성하게 됨

  ㅇ 입력, 출력
     - 입력 : 그래프 (노드 개수, 간선 개수 등), 시작 노드
     - 출력 : 통상, 출력은, 편의상, 각 노드최단 경로 길이가 담겨진 테이블 1개 정도 만 요구함
        . 최단 경로 길이 테이블 
           .. (각 노드별로, 시작 노드에서 해당 노드까지, 최단 경로 상의 가중치들의 합)
        . 추가적으로, 각 노드까지 최단 경로를 열거할 수 있는 힌트 등
           .. 최단 경로 상에 있는, 출발 직후 노드 (선행 정점) 또는 도착 직전 노드 (후행 정점) 등

  ㅇ 상태 자료구조
     - 노드 집합
        . 최단 경로를 찾은 노드 집합 (점점 커짐)
     - 최단 경로 길이 배열 
        . 각 노드별로, 노드 집합에 있는 정점 만 거쳐, 
        . 현재까지의 최단 경로 길이(최단 거리)를 갱신 저장해 두기 위함

  ㅇ 알고리즘 단계  :  (단순한 방법 : 1956년 당시 Dijkstra가 제안한 방법)
     * (초기화 단계)
     - ① `최단 경로 길이 배열(테이블)`을 초기화함
        . 최단 경로 길이 배열(테이블)
           .. 각 노드별로, 현재까지의 최단 경로 길이(최단 거리)를 갱신 저장해 두기 위함
        . 초기화
           .. 시작 정점의 경로 길이 가중치는, 영(0) 적용
           .. 나머지 모든 다른 정점의 경로 길이 가중치 값은, 무한대(∞) 적용
           .. 무한대 적용은, 도달 못할 정점도 있기 때문
     - ② 순환 방지를 위해, `이미 방문한 정점들의 집합`을 만듬
        . 초기화  :  처음에는 공집합 으로 함 (개별 원소들을 False 또는 Null 적용)
     * (반복 단계)
     - ③ 미 방문 정점들 중 최단 거리 정점을 선택 (선형 탐색 필요)
        . 매 반복 단계 마다, 현재 정점에 대한, 최단 거리가 확정됨 
     - ④ 현재 정점와 연결된(인접한) 미 방문 정점들을 확인
        . 현재 정점을 경유하는 거리와 기존 저장된 거리를 비교하여, 더 짧은 거리이면 업데이트

  ㅇ 알고리즘 단계  :  (개선된 방법)
     - ① 최단 경로 길이 배열(테이블)을 초기화함
        . 위와 상동
     - ② 순환 방지를 위해, 이미 방문한 정점들의 집합을 만듬
     - ③ 정점 방문 (by 우선순위 큐)를 만들어 감
        . 우선 그곳에 시작 정점을 넣어 둠
        . 우선순위 큐를 사용함
        . 현 정점에서 시작 정점까지 경로 길이가 짧을수록, 높은 우선순위를 줌 
     - ④ 현재 정점으로부터 미 방문 정점들 모두를 방문
     - ⑤ 방문 정점은 방문했음으로 방문했을 알리는 마크 표시
     - ⑥ 정점 방문 가 빌 때까지 단계 ④부터 되풀이

  ㅇ 시간복잡도 
     - 단순한 방법 :  O(V2)
        . 모든 정점들을, 매번 최단거리를 선형 탐색 해야 하고,
        . 현재 정점과 연결된 점정들을, 매번 일일이 확인해야 함
     - 개선된 방법 :  O(E log V)
        . 여기서, V : 노드 갯수, E : 간선 갯수

  ㅇ ... (작성중) ...


3. 벨만 포드 알고리즘 (Bellman-Ford Algorithm)

  ㅇ 1958년 Richard Bellman,1962년 Lester Ford가 제안한 알고리즘을 기반으로 함

  ㅇ 그래프 상의 특징
     - 음의 가중치도 허용하는 경우
     - 순환 포함 허용

  ㅇ 방식 상의 특징
     - 간선 가중치가 음수도 처리 가능
     - 결과를 이용하여 음수 가중치 순환을 찾아낼 수 있음

  ㅇ 시간복잡도 : O(nm)
     - (n : 정점수, m : 간선수) 

  ㅇ ... (작성중) ...

그래프 알고리즘
   1. 그래프 알고리즘   2. 그래프 순회 (DFS,BFS)   3. 깊이 우선 탐색 (DFS)   4. 너비 우선 탐색 (BFS)   5. 위상 정렬   6. 최소 신장 트리   7. 최단 경로   8. 다익스트라 알고리즘   9. 플로이드 알고리즘  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"