[理工] 請問這題演算法看不懂Ballman

[kkk22805385 (Butterlion)]

http://i.imgur.com/ByPV47j.jpg

那個表格跟平常的Bellman Ford不太一樣
-----
Sent from JPTT on my iPhone

--

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.139.84.158
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1471495706.A.DC8.html
推 krusnoopy: 你要問什麼XD 他只是把詳細過程寫下來而已阿
→ kkk22805385: 第一個圖 (b,d) 跟d那一個為什麼是5 他這樣應該是走
→ kkk22805385: 兩條吧
→ kkk22805385: 應該說 他這樣應該是a到b到d
推 krusnoopy: 因為(a,b)已經有值了,照演算法跑下來沒錯,所以到最後一
→ krusnoopy: 個iteration有些會多做,不過這不影響結果
推 krusnoopy: 也因為有這種效果,DAG才可以找到拓噗排序之後,跑一次it
→ krusnoopy: eration就完成最短路徑
→ kkk22805385: 謝謝