본문 바로가기

알고리즘/알고리즘 개념

[알고리즘] 다익스트라

다익스트라 알고리즘이란?

  • 다이나믹 프로그래밍을 활용한 대표적인 최단경로 탐색 알고리즘
    • 다이나믹 알고리즘인 이유 : 최단거리는 여러 개의 최단 거리로 이루어져있기 때문
    • 현재까지 알고 있던 최단 경로를 계속해서 갱신
  • 인공위성 GPS소프트웨어 등에서 가장 많이 사용
  • 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌
    • 음의 간선은 포함할 수 없음
    • 현실세계 -> 음의 간선 존재X
    • => 현실세계에 사용하기 매우 적합

 

과정

  • 1. 출발 노드 설정
  • 2. 출발 노드를 기준으로 각 노드의 최소비용 저장
  • 3. 방문하지 않은 노드 중에서 가장 비용이 적게드는 노드 선택
  • 4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소비용 갱신
  • 5. 3번과 4번 과정 반복