최단 경로(shortest path)
δ(u,v)={min{w(p):u→v}∞
- 다익스트라 알고리즘(그리디 알고리즘)
- 플로이드 알고리즘(동적 프로그래밍 알고리즘)
0≤i≤j≤k에 대해서
p가 v0에서 vk까지의 최단 경로일 경우,
p의 부분 경로 pij는 vi에서 vj까지의 최단 경로이다.
다익스트라, 플로이드 알고리즘은 음의 가중치를 허용하지 않는다.
벨만 포드 알고리즘 등 다른 알고리즘은 음의 가중치를 허용하기도 한다.
음의 가중치가 포함되어 있어도 순환 구조가 없으면, 동일하게 적용된다.
너비 우선 탐색을 이용하면, 순환 구조를 제외하고 그래프를 얻을 수 있다.
== 최단 경로 표현
완화(Relaxation)
지금까지 발견된 최단 경로를 개선할 수 있는 경우 검사 및 개선
int weight(Node u, Node v);
void Relax(Node u, Node v, int (*ftnW)(Node, Node)){
if(v.d>u.d+ftnW(u, v)){
v.d=u.d+ftnW(u, v);
v.pi=u;
}
}