최단 경로 알고리즘

---

최단 경로 문제

• 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제이다.
• 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다.

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 최단 경로 문제
   • 그래프 안의 특정 노드 u에서 출발하여 또 다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제이다.
2. 단일 출발 최단 경로 문제
   • 그래프 안의 특정 노드 u와 그래프 안의 모든 노드와의 가장 짧은 경로를 찾는 문제이다.
   • 그래프 안에 A, B, C, D라는 노드가 있을 때, 특정 노드를 A라고 한다면
     (A-B), (A-C), (A-D) 각각의 가장 짧은 경로를 찾는 문제를 의미한다.
3. 전체 쌍(all-pair) 최단 경로 문제
   • 그래프 안의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제이다.

다익스트라 알고리즘

---

다익스트라 알고리즘은 최단 경로 문제 종류 중, 2번 문제에 해당하는 알고리즘이다.

다익스트라 알고리즘의 로직

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법이다.
• 다익스트라 알고리즘은 너비우선탐색(BFS)과 유사하다.
  • 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후,
    첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서,
    첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트한다.

우선순위 큐를 활용한 다익스트라 알고리즘

• 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드의 정보를 앞에 저장하여 꺼내게 한다.
  1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장한다.
     • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장한다. (inf 라고 표현)
     • 우선순위 큐에 (첫 정점, 거리 0) 만 먼저 넣는다.
  2. 우선순위 큐에서 노드를 꺼낸다.
     - 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내진다.
     - 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교한다.
     - 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
     - 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
     - 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 된다.
     - 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않는다.
     (계산을 하지 않아서 계산 시간이 확 줄어든다.)
  3. 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.