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 : 간선수) 

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



"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"