이렇게 되어 새 글로 쓰게 되었는데, 계속 글이 안올라가서 고치면서 확인해보니 글 어딘가에 ^B 문자가 포함되어 있더군요....너 어디서 온거니... O(VE) 시간에 이 문제를 풀어 봅시다. V나 E나 10,000이니 O(V^2 log E) 보다야 빠르겠지요.
아이디어는:
시점과 종점을 (s, e)라 하고 e로부터의 최단거리 트리를 생각한다.
어떤 최단거리를 이루는 엣지 하나를 끊으면(끊은 엣지를 (p, q)라 하자), 이미 만들어졌던 e로부터의 최단거리 트리가 반토막이 나면서 두 트리가 생긴다.
당연히 그 두 트리를 잇는 엣지들만이 최단거리를 구성할 수 있다.
출발점 쪽의 트리의 경우 끊어진 점이 루트, 도착점 쪽의 트리의 경우 도착점이 루트이므로 (x, y)가 두 트리를 잇는 엣지라 하면 s -> p -> x -> y -> e 의 경로를 선택해야 하는데, 이 비용은:
s -> p := dist(e, s) - dist(e, p)
p -> x := dist(e, x) - dist(e, p)
x -> y := weight(x, y)
y -> e := dist(e, y) 와 같이 쉽게 계산할 수 있다.
그래서, 끝점으로부터의 최단거리 트리를 구하고(다익스트라 등을 사용하면 어디로부터 왔는지 기록하면 바로 구할 수 있겠죠) 최단거리를 구성하는 엣지들을 하나씩 잘라 보면서 트리를 두동강내고, E개의 엣지들을 모두 보면서 두 트리를 잇는지 확인하고, 잇는 경우 그 엣지를 선택하여 되돌아가는 거리를 쉽게 계산할 수 있으니 O(VE) 에 해결할 수 있습니다.
페이퍼를 찾아보실 분은 "Real Time Critical Edge of the Shortest Path in Transportation Networks, Yinfeng Xu and Huahai Yan, 2006" 을 보시면 되겠습니다. (별 새로운 이야기는 없어요)
Being
이렇게 되어 새 글로 쓰게 되었는데, 계속 글이 안올라가서 고치면서 확인해보니 글 어딘가에 ^B 문자가 포함되어 있더군요....너 어디서 온거니...
O(VE) 시간에 이 문제를 풀어 봅시다. V나 E나 10,000이니 O(V^2 log E) 보다야 빠르겠지요.
아이디어는:
그래서, 끝점으로부터의 최단거리 트리를 구하고(다익스트라 등을 사용하면 어디로부터 왔는지 기록하면 바로 구할 수 있겠죠) 최단거리를 구성하는 엣지들을 하나씩 잘라 보면서 트리를 두동강내고, E개의 엣지들을 모두 보면서 두 트리를 잇는지 확인하고, 잇는 경우 그 엣지를 선택하여 되돌아가는 거리를 쉽게 계산할 수 있으니 O(VE) 에 해결할 수 있습니다.
페이퍼를 찾아보실 분은 "Real Time Critical Edge of the Shortest Path in Transportation Networks, Yinfeng Xu and Huahai Yan, 2006" 을 보시면 되겠습니다. (별 새로운 이야기는 없어요)
15년 전