가중치 그래프 G = (V,E), 즉 모든 edge에 가중치가 있다.
방향그래프이냐 무방향 그래프이냐는 별로 중요하지 않다.
경로 p=(v0,v1,....,vk)의 길이는 경로상의 모든 엣지의 가중치의 합
BFS의 경우 edge의 갯수가 경로의 길이가 될 때,
모든 edge의 weight가 다 1이거나 모두 동일하다면 edge의 갯수가 가장 작은 경로가 최단 경로가 된다.
이런 경우에는 BFS 알고리즘 만으로도 최단 경로를 구할 수 있다.
single-source :
하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾는 방식(다익스트라)
single destination :
모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾는 방식
무방향 그래프일 때는 이 두가지 방식이 똑같다.
All-pairs :
모든 노드 쌍에 대해서 최단 경로를 찾는 방식(플로이드 와샬)
음수 가중치
음수 사이클(negative cycle)이 있으면 최단 경로가 정의되지 않는다.
최단 경로는 사이클을 포함하지 않는다.(음수 사이클이 없다는 가정하에)
사이클을 도는 경로가 0보다 크기 때문에 애초에 사이클을 돌 필요가 없다.
single-source 최단 경로 문제
입력: 음수 사이클이 없는 가중치 방향 그래프 G=(V,E) 와 출발 노드 s∈V
목적: 각 노드 v∈V에 대해서 다음을 계산한다.
- d[v]
처음에는 d[s] = 0, d[v] = ∞으로 시작
알고리즘이 진행됨에 따라 감소한다.
최종적으로는 d[v]가 s에서 v까지 가는 최단경로 길이가 된다.
하지만 최종 목표가 최단경로의 길이를 구하는 것이 아니라 경로 자체를 구하는 것이다. - π[v]
s에서 v까지의 최단 경로상에서 v의 직전 노드(predecessor)
그런 노드가 없는 경우 π[v]=NIL
Relaxation
더 나은 경로가 있으면 업데이트 해주는 연산
어떤 edge에 대해서 relax한다.
(u,v)가 2이다.
u에서 v로 가는 어떤 edge에 대해서 relax한다는 것은,
동그라미 안에 있는 숫자는
d[u] = 5
현재까지 출발점 s로 부터 u까지 가는 길이가 5인 경로를 하나 찾았다. 이런 의미이다.
(현재까지 알고있는 경로는 5이다..)
최단 거리가 5라고 보장할 수는 없다.
d[v] = 9
s에서 v까지 가는 가장 좋은 길이는 9다.
v의 입장에서 지금까지 알고 있는 최단 경로의 길이는 9 인데,
s에서 u까지 5로 가는 경로가 존재하고, (u,v) edge의 weight가 2이다.
v의 입장에서 기존에 알고 있던 9보다 s에서 u로 간다음 u에서 v로 오는 것이 7이 된다.
기존에 알고있던 경로보다 더 나은 경로를 하나 발견한 것이다.
d[v] = 7로 업데이트하고,
π[v]= u가 된다.
Relax(u,v,w)
if d[v] > d[u] + w(u,v)
then d[v] <- d[u] + w(u,v)
π[v] <- u
Generic-Single-Source(G,w,s)
d[s] = 0, d[v] = inf (not s), π[v] = NIL
repeat
for each edge (u,v)
Relax(i,v,w)
until there is no change.반복을 N-1번 하면 충분하다.
Bellman-Ford 알고리즘
단순히 최단경로를 찾을 뿐만 아니라 음수 사이클이 있는 경우에 알아낼 수 있다.
Bellman-Ford(G,w,s)
initalize(G,s)
for i<-1 to |V[G]| -1
do for each edge (u,v)
do Relax(u,v,w)
for each edge (u,v)
do if d[v] > d[u] + w(u,v)
then return FALSE
return TRUE사실 Relax까지 for문을 다 돌고나면 모든 edge들로 가는 최단 거리가 구해진 상태이다.
그 다음 for문으로 relax연산과 같이 검사를 시도했을 때,
변화가 생기면 안된다. 왜냐하면 이미 모든 노드의 최단거리 다 찾아졌기 때문이다.
그래서 추가로 더 relax가 가능해진다면, 이것은 음수 사이클이 존재한다는 의미가 된다.
시간복잡도는 O(VE)
Dijkstra 알고리즘
초기화부분은 벨만포드와 똑같다.
벨만포드와 다른점은 모든 edge를 매순간 relaxation하지 않아도 된다는 것이다.
무한인 노드들 중에서 현재 거리가 가장 적은 노드를 찾는다.
최소인 노드로 부터 갈 수 있는 edge들만 relaxation을 한다.
위의 그래프인 경우,
가장 먼저 s가 시작점이고 s로 부터 갈 수 있는 5와 10에 대해서 relaxation을 한다.
그러면 위의 노드는 10으로 업데이트가 되고,
아래로 가는 노드는 5로 업데이트가 된다.
다음으로는 s노드는 출발점에서 s로 가는 최단 거리값이 고정이 되기 때문에, 그 노드로 부터 나가는 모든 노드를
다시 relax할 이유가 없다.
결론적으로 한번 선택이 되어서 그 노드에서 나가는 edge들을 relax한 노드들은 선택의 대상에서 제외가 된다.
두번째로, 선택한 노드를 제외하고 나머지 노드들 중에서 거리가 가장 짧은 노드를 선택한다.
10은 s에서 가는 최단 길이라고 보장할 수 없다.
5인 노드는 s에서 가는 최단 길이다.
따라서, 5인 노드를 선택하게 되고 5에서 갈 수 있는 모든 edge들을 relax한다.
결과적으로 모든 노드들이 가지고 있는 d[v]의 값이 시작점에서 각각의 노드로 가는 최단 경로의 길이가 된다.
특징
음수 가중치가 없다고 가정
Dijkstra(G,w,s)
for each v do
d[v] = inf
π[v] = NIL
end.
S = NIL
d[s] = 0
while |S| < n do //집합에 모든 노드가 추가 될 때 까지
find u not in S with the mininum d[u] value; //최소값을 찾을 때 O(n)
S 에 u를 추가
for each V not in S adjacent to u do //degree(u) = O(n)
if d[v] > d[u] + w(u,v) then
d[v] <- d[u] + w(u,v)
π[v] <- u
end
end
end
시간 복잡도는 O(n^2)
최소값을 찾을 때 우선순위 큐를 사용하게 된다면 O(Mlogn)
