作者ekids1234 (∵:☆星痕╭☆)
看板Grad-ProbAsk
標題[理工] Dijkstra algo
時間Sat Sep 21 01:45:17 2019
各位好
想請教一下關於 Dijkstra 的 Pseudo Code
https://i.imgur.com/3CO4NP4.png
其實我不知道 S 在這個 Code 的存在意義是什麼
在實作上的確會有 int passed[n] 之類的來記錄是否經過了沒錯
並且在 Relax 的 if 那邊新增確定沒走過
但 Pseduo Code 並沒有對這部分多說明 (我是看林立宇講義 + wiki)
G.adj[u] 理論上也不會去做更動
另外，如果多去記錄有無走過，應該也無法讓程式 複雜度降低
就是多少省一點這樣 ?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.107.244.180 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1569001521.A.A5F.html
<應推文作者將前推文移除>
1F：→ DLHZ: 抱歉 S的確可以移掉 是我看錯 09/21 02:39
2F：→ DLHZ: 有點亂 你願意的話把我多餘的廢話刪掉吧 09/21 02:41
好的，這樣 Pesduo 感覺又能更簡潔一點 ~
※ 編輯: ekids1234 (106.107.244.180 臺灣), 09/21/2019 09:35:13
3F：推 FRAXIS: 是不是證明裡面有用到啊？ 09/21 11:08
4F：→ mathtsai: Q = V-S 09/21 14:48
5F：→ mathtsai: 不然按照這個code 沒辦法排掉已經決定過的vertex 09/21 14:50
6F：→ DLHZ: 第五行除了取出最小的點應該也有同時在Q裡去掉？ 09/21 16:20
Extract-Min 應該有做類似 pop 的動作沒錯，
我們在討論用 Binary Heap 做 Priority Queue 時
複雜度給他 log(|V|) 就算是包括踢出去 + 調整 Tree 了
7F：→ mathtsai: 愈想愈怪 因為實作的時候 只有處理Q和relax而已 09/21 18:14
8F：→ 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
9F：推 mistel: 其實我覺得是操作的時候會用到提醒一下學生XD，不然你看 09/22 00:36
10F：→ mistel: 後面的Prim's確實沒有（雖然兩個處理不同問題但概念很像 09/22 00:36
11F：→ mistel: ） 我認為追蹤的話應該是掃一遍所有點的狀態，就像原po大 09/22 00:36
12F：→ mistel: 大說的一樣 09/22 00:36
13F：推 b10007034: 交大江蕙如 Lec12剛好有提到，在45:07之後 09/23 09:59