[理工] [algo] shortest path tree

[mqazz1 (無法顯示)]

1. the input graph G has a shortest path tree if and only if G does not contain

any negative cycle


2. the shortest path tree problem is equivalent to find the distance from r

to each node u in graph G



請問這兩件事應該要怎麼證明呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.24.121
推 kib65060:1.用反證法，先說你有一個最短路徑
→ kib65060:然後說因為圖裡有nagtive cycle
→ kib65060:矛盾
推 kib65060:因為你可利用nagtive cycle 找到更短的路徑
推 FRAXIS:path本來就沒有cycle 就算有negative cycle,
→ FRAXIS:shortest path還是存在  只是我不知道tree還存不存在..
→ privatewind:path允許cycle吧...但不允許有loop
推 FRAXIS:cycle跟loop差在哪？
推 privatewind:loop指的是 a->a cycle則是指至少三點
→ privatewind:且不能有loop
→ privatewind:所以cycle可以a->b->a
推 FRAXIS:那就看你怎麼定義path囉 有書的定義是path不能重複點
→ FRAXIS:可以重複點的叫做 Walk 也有書說path可以重複點
→ FRAXIS:沒有重複點的path叫做simple path
→ sneak: path本來就沒有cy https://daxiv.com