[問題] strongly connected directed
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
→
11/02 22:39, , 1F
11/02 22:39, 1F
→
11/03 19:23, , 2F
11/03 19:23, 2F
→
11/05 22:49, , 3F
11/05 22:49, 3F
→
11/05 22:50, , 4F
11/05 22:50, 4F
→
11/05 22:50, , 5F
11/05 22:50, 5F
→
11/05 22:51, , 6F
11/05 22:51, 6F
推
11/06 00:01, , 7F
11/06 00:01, 7F