[問題] strongly connected directed

[mqazz1 (無法顯示)]

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
→ tkcn:想想 +s(u)-s(v) 的意義，一正一負是有原因的
→ suhorng:分項對消(?)
→ suhorng:就是 你可以看出來 對於圖中的任一條路徑
→ suhorng:其邊權和會是原本路徑的邊權和 加減某一常數
→ suhorng:所以最短路不變 (? 因為仍有最優子結構?
→ suhorng:啊...這樣講好怪ˊˋ 我再想想 抱歉orz
推 DJWS:CLRS的Johnson's algorithm for sparse graphs小節有證明過程