Dijkstra's Algorithm   다익스트라 알고리즘

(2021-02-21)

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) : 네덜란드 과학자

  ㅇ 그래프 상의 특징
     - 간선에서 음의 가중치를 허용 않음
     - 순환 포함 허용

  ㅇ 방식 상의 특징
     - 첫 출발 정점을 기준으로, 연결된 정점들을 추가해가며, 최단 거리를 갱신해 감
     - 시작 정점에서 모든 다른 정점까지의 최단 경로들은, 신장 트리를 형성하게 됨

  ㅇ 입력,출력
     - 입력 : 그래프, 시작 노드
     - 출력 : 두 배열
        . 최단 경로 길이 (각각의 최단 경로 상의 가중치들의 합)
        . 최단 경로 상에 있는 출발 직후 노드 또는 도착 직전 노드알고리즘 단계
     - ① 시작 정점의 경로 길이 가중치를 영(0),
          나머지 모든 다른 정점의 경로 길이 가중치 값을 무한대(∞) 적용
        . 이는 도달 못할 정점도 있기 때문
     - ② 순환 방지를 위해, 이미 방문한 정점들의 집합을 만들어 감
     - ③ 정점 방문 를 만들어둠
        . 우선 그곳에 시작 정점을 넣어 둠
        . 이는 우선순위 를 위함이며, 우선순위는 정점까지의 경로길이고, 
        . 현 정점에서 시작 정점까지 경로 길이가 짧을수록 높은 우선순위를 줌 
     - ④ 현재 정점으로부터 미 방문 정점들 모두를 방문
     - ⑤ 방문 정점은 방문했음으로 방문했을 알리는 마크 표시
     - ⑥ 정점 방문 가 빌 때까지 단계 ④부터 되풀이

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


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

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

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

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

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

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


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 (DFS,BFS) 3. 위상 정렬 4. 최소비용 신장트리 5. 최단 경로 6. 다익스트라 알고리즘 7. 플로이드 알고리즘

 
        최근수정     요약목록     참고문헌