作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] strongly connected directed
时间Tue Nov 2 22:27:52 2010
consider a strongly connected directed graph G = (V,E),
which has negative-length edges, but has no negative-length cycles
let L(u, v) denote the length of an edge (u,v)属於E,
and d(u,v) denote the shortest path distance from vertex u to vertex v
assume that a value s(v) is attached to each vertex v属於V on the graph G
consider a new graph G' that comes from transforming G by replacing the
legth of each edge (u,v)属於E with L(u,v) + s(u) - s(v)
prove that the shortest path on the graph G' between w属於V and x属於V
is also the shortest path between w and x on the graph G
请问这个问题要怎麽证明比较好?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.166.118.154
1F：→ tkcn:想想 +s(u)-s(v) 的意义，一正一负是有原因的 11/02 22:39
2F：→ suhorng:分项对消(?) 11/03 19:23
3F：→ suhorng:就是 你可以看出来 对於图中的任一条路径 11/05 22:49
4F：→ suhorng:其边权和会是原本路径的边权和 加减某一常数 11/05 22:50
5F：→ suhorng:所以最短路不变 (? 因为仍有最优子结构? 11/05 22:50
6F：→ suhorng:啊...这样讲好怪ˊˋ 我再想想 抱歉orz 11/05 22:51
7F：推 DJWS:CLRS的Johnson's algorithm for sparse graphs小节有证明过程 11/06 00:01