youtube:동빈나_Dijkstra Algorithm

다익스트라(Dikstra)알고리즘

• 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path) 탐색 알고리즘
• 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용
• 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌
  but 이때 음의 간선을 포함할 수 없음 (물론 현실에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나)
• 다익스트라 알고리즘이 다이나믹 프로그래밍 문제에도 해당하는 이유? '최단거리는 여러 개의 최단 거리로 이루어져있기 때문'
  = 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있음
• 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용함

다익스트라 알고리즘 예제

• 1과 당장 붙어있는 노드인 2,3,4까지 최단 거리를 각각 3,6,7로 산정 가능
• why? 컴퓨터는 당장 하나씩 밖에 계산하지 못하기에
• eg. 1에서 3까지 가는 최소 비용 = 6

• 이후 다음과 같이 다음 노드인 2를 처리하게 되었다고 가정

• 위와 같이 나중에 컴퓨터는 경로 1 -> 3의 비용이 6인데 1-2-3이 총 비용 4로 더 저렴하다는 걸 알게 됌
• 이 때 현재까지 알고 있던 3으로 가는 최소 비용 6을 새롭게 4로 갱신
  ∴ '현재까지 알고 있던 최단 경로를 계속해서 갱신'함

구체적인 작동 과정
1. 출발 노드를 설정
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐서 특정한 노드로 가는 경우르 고려하여 최소 비용 갱신
5. 끝날때까지 위 과정 3번 ~ 4번 반복

예시

• 위와 같은 그패프는 실제로 컴퓨터 안에서 처리할 때 이차원 배열 형태로 처리해야 함
• 아래 표의 의미 : 특정 행에서 열로 가는 비용 eg. 1행 3열의 값 5 : 1번 노드에서 3번 노드로 가는 비용이 5라는 의미
  eg. 1노드->1노드 : 자신이므로
  1노드->2노드 : 2
  현재 5노드와 6노드는 1노드와 바로 연결되어 있지않기 때문에 : 무한
  

• 노드 1을 선택한 상태, 이와 연결된 세 개의 간선 확인한 상태
• 1번 노드에서 다른 정점으로 가는 최소 비용은 다음과 같음
• 배열을 만든 뒤에는 이 최소 비용 배열을 계속해서 갱신할 것임
• 현재 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 4번 노드
  
  ∴ 위 배열 상태를 고려하여 4번 노드가 선택되었음 : 4번 노드를 거쳐서 가는 경우를 모두 고려하여 최소 비용 배열 갱신

• 기존 5로 가는 최소 비용은 무한이었음 but 4를 거쳐서 5로 가는 경우 비용이 2이므로 최소 비용 배열 갱신
• also 4를 거쳐 3으로 가는 경우는 비용이 4이므로 기존보다 더 저렴하므로 최소 비용 배열 갱신
  

C언어 소스코드 구현