→ DLHZ: 抱歉 S的確可以移掉 是我看錯 09/21 02:39
→ DLHZ: 有點亂 你願意的話把我多餘的廢話刪掉吧 09/21 02:41
好的，這樣 Pesduo 感覺又能更簡潔一點 ~
※ 編輯: ekids1234 (106.107.244.180 臺灣), 09/21/2019 09:35:13
推 FRAXIS: 是不是證明裡面有用到啊？ 09/21 11:08
→ mathtsai: Q = V-S 09/21 14:48
→ mathtsai: 不然按照這個code 沒辦法排掉已經決定過的vertex 09/21 14:50
→ DLHZ: 第五行除了取出最小的點應該也有同時在Q裡去掉？ 09/21 16:20
Extract-Min 應該有做類似 pop 的動作沒錯，
我們在討論用 Binary Heap 做 Priority Queue 時
複雜度給他 log(|V|) 就算是包括踢出去 + 調整 Tree 了
→ mathtsai: 愈想愈怪 因為實作的時候 只有處理Q和relax而已 09/21 18:14
→ mathtsai: 確實沒有處理S的部分 09/21 18:15
補一下教材的照片
解說有提到，但看他那樣說我還是不知道紀錄的用途
https://i.imgur.com/mUfUDWf.jpg
還是說可以用來做追蹤 ?
一般來說如果要 track back 整條 shortest path 的話
應該是利用 Relax 內，更新 v.distance 時 順便紀錄其 parent
這樣就能追蹤了
附一下一題 example，他寫了 S\v (v代表 u->v )
https://i.imgur.com/26sozjc.jpg
不知道有沒有特殊用途，拓樸(Topological) ? (還是這例子太簡單了剛好而已)
※ 編輯: ekids1234 (106.107.244.180 臺灣), 09/21/2019 20:41:07
推 mistel: 其實我覺得是操作的時候會用到提醒一下學生XD，不然你看 09/22 00:36
→ mistel: 後面的Prim's確實沒有（雖然兩個處理不同問題但概念很像 09/22 00:36
→ mistel: ） 我認為追蹤的話應該是掃一遍所有點的狀態，就像原po大 09/22 00:36
→ mistel: 大說的一樣 09/22 00:36
推 b10007034: 交大江蕙如 Lec12剛好有提到，在45:07之後 09/23 09:59