[問題] strongly connected directed
看板Prob_Solve (計算數學 Problem Solving)作者mqazz1 (無法顯示)時間14年前 (2010/11/02 22:27)推噓1(1推 0噓 6→)留言7則, 3人參與討論串1/1
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
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
