최단경로 알고리즘

최단경로

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

최단경로 문제의 종류

1. 단일 출발 최단경로 문제
   • 그래프 내의 특정 노드 a에서 출발해 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 도착 최단경로 문제
   • 모든 노드들로부터 출발하여 그래프 내의 특정 노드 z로 도착하는 가장 짧은 경로를 찾는 문제
3. 단일 쌍 최단 경로 문제
   • 주어진 노드 a와 z간의 최단경로를 찾는 문제
4. 전체 쌍 최단경로 문제
   • 그래프 내의 모든 쌍(a,z) 사이에 대한 최단경로를 찾는 문제

다익스트라 알고리즘

• 최단경로 문제중 1번에 해당하며 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제에서 활용되는 알고리즘이다.

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

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가하며 최단 거리를 갱신한다.
• BFS(너비우선 탐색)과 유사하다.

  첫 정점부터 각 노드간의 거리를 저장하는 배열을 만들고 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트를 한다.