최단 경로 알고리즘

 ( 강의 출처 : https://www.youtube.com/watch?v=acqm9mM1P6o&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=7&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 )

최단 경로 알고리즘
 : 가장 짧은 경로를 찾는 알고리즘 

 : 다익스트라 최단 경로 알고리즘
     특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
     음의 간선이 없을 때 정상적으로 동작한다.
     ( 현실 세계의 간선은 음의 간선으로 표현되지 않음 )
     다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨
     : 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복.
     또한, 최단경로 알고리즘은 다이나믹 프로그래밍의 분류에 속하기도 함.

     다익스트라가 제시한 알고리즘 중 최단 경로에 대한 알고리즘을 알아보자.
     1. 출발 노드 설정
     2. 최단 거리 테이블을 초기화
     3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 ( 그리디 알고리즘의 요소 )
     4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
        ( 경로를 구하는 것은 아니고 거리를 구할 수 있게 됨. 일반적인 코딩테스트 수준에서는 
          경로까지 구하는 것은 출제되지 않음 )
     5. 3번과 4번을 반복 ( 다이나믹 프로그래밍의 요소 )

     3번이 성립하는 이유는 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하면
     해당 노드까지 최단 거리가 변하지 않기 떄문이다.
     즉, 한 단계단 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

     경로를 구하기 위해서는 추가적인 기능을 작성해야 한다.

     다익스트라 최단 경로 알고리즘은 총 O(n)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야한다.
     그렇기 때문에 시간복잡도는 O(n^2) 이다.

     이를 좀 더 효율적으로 활용하기위해,
     우선순위 큐 ( Priority Queue )를 사용해야 한다.

 : 우선순위 큐 ( Priority Queue ) 는 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 이다.
     간단하게 복습차 간단히 다시 짚고 넘어가자.
     스택 ( Stack ) : FILO
     큐 ( Queue ) : FIFO
     우선순위 큐 : 가장 우선순위가 높은 데이터 먼저 추출.
                       ( 최소 힙은 값이 낮은 데이터부터, 최대 힙은 값이 높은 데이터부터 추출한다. )


     이때, 우선순위 큐를 구현하는 자료구조 중 힙 ( Heap) 이 사용되기도 한다.
     우선순위 큐를 구현하는데에 사용하는 자료구조에따라 차이점이 있는데
                          삽입 시간      삭제 시간
     리스트 사용시 :     O(1)              O(N)
        힙   사용시 :    O(log n)        O(log n)
     
     리스트 사용시 삽입 시에는 맨 마지막에 데이터를 추가하면 되기때문에 O(1)의 시간복잡도를 갖고,
     삭제하는 경우에는 전체 데이터를 순회하여, 

     가장 우선순위가 높은 데이터를 추출하기에 O(n)의 시간복잡도를 갖는다.

     힙은 내부적으로 트리구조로 구현되어 O(log n)의 시간복잡도를 갖도록 구현할 수 있다.

     추가적으로 Priority Queue는 기존에 자료구조를 공부할때처럼 .add() 메소드로 원소를 추가할 수도 있지만,
     .offer()를 통해서도 원소를 추가할 수 있다.
     .add() 메소드는 원소 추가에 실패한 경우, 예외를 발생시키며
     .offer() 메소드는 원소 추가에 실패한 경우 false를 반환하게 된다.

     최소 힙 자료구조를 사용하는 다익스트라 알고리즘의 시간복잡도는 O(n log n ) 이다.
      : 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 이상으로 처리되지 않음
     결과 적으로 현재 우선순위 큐에서 꺼낸 노드와 다른 노드들을 확인하는 
     총 횟수는 최대 간선의 개수만큼 연산이 진행될 수 있음

     전체 과정은 n개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사하다.
      : 시간복잡도를 O(n log n)으로 판단할 수 있다. 
     ( 본 강의에 직관적으로, 하고 적혀있지만 개인적으로 직관적으로 다가오지 않아 
      제외하였으며, 좀 익숙해질 필요가 있는 것 같다. )


 : 플로이드 워셜 알고리즘
     모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.
     플로이드 워셜 ( Floyd-Warshall ) 알고리즘은 

     다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로
     알고리즘을 수행한다.
       : 다만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.
     플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.
     플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.

     각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.
     a에서 b로 가는 최단 거리보다, a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.

     점화식 : Dab = min(Dab, Dak+Dkb)

     노드의 개수가 N개 일떄, 알고리즘상 N번의 단계를 수행한다.
     그리고 그 단계는 O(n^2)의 연사을 통해 현재 노드를 거쳐가는 모든 경로를 고려하므로, 총 시간복잡도는 O(n^3)이다.