Shortest Path Problem(최단 경로 문제)
- 정점 u 에서 v까지의 최단 경로 : 정점 u에서 정점 v까지의 경로 중에 경로의 값이 가장 작은 경로
- 정점 u를 시작점(source), 정점 v를 도착점(destination) 이라고 한다.
- δ(u,v) : u에서 v까지의 최단 경로 값
- negative-weight cycles이 있으면 최단경로 문제는 정의되지 않는다. δ(u,v)=-∞가 나올 수 있음
- positive-weight cycles, zero-weight cycles 는 구할 수 있다. (사이클 무시하면 됨)
- optimal substructure theorem(최적부분 구조 : 분할된 문제의 결과가 매번 같다)으로 greedy sub를 만족한다.
- δ(s,v) ≤δ(s,u)+δ(u,v) 가 항상 성립한다.
- d[v] : 최단거리 추청치. 초기값 : d[v]=∞, d[v]->δ(s,v)
- 𝝅[v] : s에서 v로 갈 때의 전인자. 전인자 없으면 𝝅[v]=NIL(초기값), 𝝅를 이은 트리를 shortest-path tree라고 부른다.
- Relazation : d[v]를 더 줄일 수 있는지 테스트. 즉 더 빠른길이 있는지를 테스트하여 존재하면 값을 변경한다.
최단경로 문제의 종류
- Single-Source Single-Destination(1-1) : 시작점 1개 도착점 1개
- Single-Source All-Destination(1-M) : 시작점 1개, 도착점 여러개
- All-Sources Single-Destination(M-1) : 시작점 여러개, 도착점 1개
- All-Sources All-Destinations(M-M) : 시작점 여러개, 도착점 여러개
Bellman-Ford Algorithm(벨만 포드 알고리즘)
initialization, Relaxation 으로 연산한다.
음의 간선이 있는 경우에도 문제를 해결할 수 있다.
negative weight cycles가 있는지 없는지 확인하는 작업 필요
간선을 기준으로 진행한다.
estimate d[v]는 진행될수록 점점 작아진다.
O(VE)
Dijkstra's Algorithm(다익스트라 알고리즘)
initialization, Relaxation 으로 연산한다.
Greedy 알고리즘
매번 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다.
벨만포드보다 빠르다.
음의 간선을 허용하지 않는다. 즉 negative weight cycles를 확인할 필요 없음
노드를 기준으로 진행한다. 각 단계를 시작할 때 가장 작은값을 우선적으로 확인한다.
min priority queue, heap으로 Greedy choice를 구현한다.
O(ElogV)
'💚알고리즘' 카테고리의 다른 글
| P and NP (P NP 문제) (0) | 2023.01.25 |
|---|---|
| Minimum SpanningTree(최소 비용 신장 트리) (1) | 2023.01.25 |
| Greedy Algorithm(그리디 알고리즘) (1) | 2023.01.25 |
| Dynamic Programming (동적 계획법) (0) | 2023.01.25 |
| Binary Search Tree (이진 탐색 트리) (0) | 2023.01.25 |
