Shortest Path   최단 경로

(2020-07-31)

최적 경로, Dijkstra's Algorithm, Dijkstra 알고리즘, 다익스트라 알고리즘

1. 최단 경로그래프 이론에서 출발지와 목적지 사이 링크들의 가중치 합이 최소가 되는 경로
     - 경로 길이(Path Length)  :  경로 상에 있는 각각의 링크들이 갖는 가중치들의 합
        . 가중치 기준 例 : 거리,시간,비용 등 
     - 최단 경로(Shortest Path)  :  모든 가능한 경로 중 최소 경로 길이를 갖는 경로


2. 최단 경로를 찾는 문제

  ㅇ 다양한 경로들 중에 가장 빠른 경로를 찾는 문제

  ㅇ 최단 경로 문제의 종류
     - 단일 출발지,목적지 최단 경로 문제 (single source, single destination shortest path problem)
        . 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제
        . 또는, 단일 쌍 최단경로 문제 라고도 함
     - 단일 출발지 최단경로 문제 (single source shortest paths problem)
        . 하나의 출발 정점에서 임의 다른 모든 정점에 대한 최단 경로를 찾는 문제
        . 총 n개 정점에서, (n-1)개의 경로를 구하는 문제
        . 例) 다익스트라 알고리즘, 벨만 포드 알고리즘 등
     - 단일 도착지 최단경로 문제 (single destination shortest path problem)
        . 하나의 목적지로 가는 모든 최단 경로를 찾는 문제
     - 모든 쌍 최단경로 문제 (all parts shortest paths problem)
        . 총 n개 정점에서, n(n-1)개의 경로를 구하는 문제
        . 例) 플로이드 알고리즘 등
     - 도달 가능성 문제

  ㅇ 초기 가정
     - 정점을 잇기 전까지는, 시작점을 제외한 모든 정점들은 가중치를 무한대(∞)로 간주 함


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

  ㅇ Dijkstra가 1956년에 개발하고, 1959년에 발표한 최단 경로 계산 알고리즘
     - Edsger W. Dijkstra (1930~2002) : 네덜란드 과학자

  ㅇ 첫 출발 정점을 기준으로, 연결된 정점들을 추가해가며, 최단 거리를 갱신해 가는 것

  ㅇ 시작 정점에서 모든 다른 정점까지의 최단 경로는, 신장 트리를 형성하게 됨

  ㅇ 음의 가중치를 허용 않는 일반적인 경우

  ㅇ 입력,출력
     - 입력 : 그래프, 시작 노드
     - 출력 : 두 배열
        . 최단 경로 상에 있는 첫 노드
        . 최단 경로의 길이

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


4. 벨만 포드 알고리즘

  ㅇ 음의 가중치도 허용하는 경우

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


[그래프 알고리즘] 1. 그래프 알고리즘 2. 그래프 순회 (DFS,BFS) 3. 최단 경로 4. 최소비용 신장트리
  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. 그래프 표현
            1.   그래프 용어
            2.   그래프 알고리즘
              1.   1. 그래프 알고리즘
                  2. 그래프 순회 (DFS,BFS)
                  3. 최단 경로
                  4. 최소비용 신장트리
          2.   트리
        3.   기타 자료구조
        4.   자료구조 기타일반
      6.   알고리즘
      7.   시스템 소프트웨어
      8.   프로그래밍언어 종류
      9.   프로그래밍 기타일반
    4.   데이터베이스
    5.   소프트웨어 공학
    6.   운영체제
    7.   정보보호/보안
    8.   IT 기타기술
  8.   공학일반(기계,재료등)
  9.   표준/계측/품질
  10.   기술경영

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