1. Dijkstra Algorithm (non-negative edge SSSP)
- Negative edge weight -> can make negative weight cycle
- Design: Greedy Algorithm
- Time Complexity: O(v^2), |V|=n, --> O(n^2) (힙 사용 시, O(E log V))
- From a starting vertex S -> find SSSP
RELAX(u, v, w)
if d[v] > d[u] + w(u,v)
then d[v] = d[u] + w(u, v)
pi[v] <- u (경로에 추가)
2. Bellman-Ford Algorithm (negative edges)
- If negative weight edges are present,
algorithm should find negative weight cycles: detect/report
- Negative weight cycle 문제 -> detect and report
- Design: DP
- Time Complexity: O(VE)
- 동작 방식:
1 ~ V-1 반복: 정상적인 최단 거리 계산
V 반복:
Relax가 일어난다? → ❗ 음의 사이클 존재!
아무 일도 안 일어난다? →✅ 최단 거리 잘 계산된 것
Initialize ()
for i = 1 to V - 1
for each edge (u, v) € E:
Relax(u, v)
for each edge (u, v) € E
do if d[v] > d[u] + w(u, v)
then report a negative-weight cycle exists
Dijkstra and Bellman-Ford : for SSSP
1. idea:
- Dijkstra (find the closest v from S -> relax -> ...)
- Bellman (simply relax ALL edges for [V|-1 time)
-> Adjacent matrix updated repeatedly.
2. 구현난이도: Bellman << Dijkstra
3. time complexity: Bellman O(VE) = O(n^3) < Dijkstra O(n^2=V^2)
(|E| = n(n-1)/2)
4. Negative weight cycle: Bellman (o), Dijkstra(x).
5 . ** Key point (design 관점)
-> Dijkstra: Greedy design
-> Bellman-Ford: DP design.
subproblem: SP v -> t, update edge 1개, 2개, 3개
vysryoo