최단경로 알고리즘 정리

November 24, 2020

참고 : 최단거리 알고리즘의 분류

Single-source: Find shortest paths from a given source vertex s ∈V to every vertex v ∈ V.
Single-destination: Find shortest paths to a given destination vertex.
Single-pair: Find shortest path from u to v.
All-pairs: Find shortest path from u to v for all u, v ∈ V.

1. 다익스트라 알고리즘 (Dijkstra Algorithm)

용도 : Single Source Shortest Path
- 그래프의 어떤 정점 하나를 대상으로, 나머지 정점들로의 최단거리를 구한다
시간복잡도 : \(O(ElogV)\)
중요 포인트
- 노드를 순회하면서 하나씩 최단거리를 ‘확정’해나간다
특징 및 유의 사항
- 모든 노드에 대해 단 한번씩만 ‘방문 처리’를 수행한다
- 가장 짧은 최단 거리를 가진 노드부터 ‘방문 처리’가 수행됨
- Directed / Undirected Graph 둘 다 사용 가능
- 간선 cost가 음수가 아닐 경우에만 사용 가능
  - cost가 음수일 경우 –> 벨만 포드 (Bellman Ford) 알고리즘
- 본질적으로 ‘Weighted Version of BFS’
  - 다른점은 Queue가 아닌 Priority Queue를 사용한다는 것
간단한 알고리즘 설명
1. 시작점일 경우 : 시작점을 방문한다
2. 시작점이 아닐 경우 : ‘방문하지 않은 노드들’ 중 ‘최단거리인 노드’를 방문한다
3. (1,2)번의 정점 기준, ‘인접 노드들’의 최단거리를 갱신한다
2번에서 ‘최단거리인 노드’를 어떻게 선택할 것인가 : Priority Queue
- 3번 과정에서 최단거리를 갱신할 때
  - (거리, 노드) 쌍을 우선순위 큐에 넣는다 (minHeap을 이용해 구현)
  - 우선순위 큐를 이용해 ‘방문하지 않은 노드들’ 중 ‘최단거리인 노드’를 선택한다
Pseudo Code

DijkstraPseudoCode

Bellman-FordPPTimage

PPT 설명
- Single Source ‘S’를 가정하고 있다
- \(d[v]\)는 그냥 거리, \(\pi[v]\)는 최단거리
- Allows negative edge
  - Negative Cycle이 나올 수 있는 가능성이 존재한다
  - 이를 막기 위해 negative cycle을 체크하는 코드가 들어가 있다
용도 : Single Source Shortest Path
시간복잡도 : \(O(VE)\)
특징 및 유의사항
- 모든 edge에 대해 Relaxation을 \(V-1\)번 수행 (edge당 \(V-1\))
  - 모든 edge에 대해 Relaxation을 수행할 때마다, ‘최단거리가 구해진 정점’ 목록에 정점이 하나씩 추가된다고 해석할 수 있음

용도 : All Pairs Shortest Path
시간복잡도 : \(O(n^3)\)
또 다른 DP 방식의 알고리즘
아이디어
- \(d_{i,j}^{(k)}\) = \(\{1,2,...,k\}\) 집합 안의 의 vertex로 이루어진, i->j 최단거리
- 가능한 intermediate vertex set을 제한하고
- k를 증가시키면서, 이 intermediate vertex set을 recursively 확장

Floyd-Warshall

참고)
- 다른 SSP 알고리즘을 All pair에 적용하면
  - 다익스트라 : \(O(V^2E)\)
  - 벨만 포드 : \(O(VElogV)\)