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. 플로이드 알고리즘
  1.   기술공통
  2.   기초과학
  3.   진동/파동
  4.   전기전자공학
  5.   방송/멀티미디어/정보이론
  6.   통신/네트워킹
  7.   정보기술(IT)
        1. 정보기술
    1.   전산기초
    2.   컴퓨터구조
    3.   프로그래밍
          1. 프로그램, 프로그래밍
      1.   프로그래밍 언어론
      2.   프로그래밍 방법론
      3.   객체지향 프로그래밍
      4.   자료표현코드
      5.   자료구조
            1. 자료구조
            2. 자료구조 종류
        1.   선형 자료구조 (리스트 등)
        2.   비선형 자료구조 (그래프,트리)
          1.   그래프
                1. 그래프
                2. 그래프 종류
                3. 그래프 표현
                4. 평면 그래프
            1.   그래프 용어
            2.   그래프 알고리즘
              1.   1. 그래프 알고리즘
                  2. 그래프 순회 (DFS,BFS)
                  3. 위상 정렬
                  4. 최소비용 신장트리
                  5. 최단 경로
                  6. 다익스트라 알고리즘
                  7. 플로이드 알고리즘
          2.   트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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