[理工] Dijkstra algo
各位好
想請教一下關於 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1569001521.A.A5F.html
<應推文作者將前推文移除>
→
09/21 02:39,
6年前
, 1F
09/21 02:39, 1F
→
09/21 02:41,
6年前
, 2F
09/21 02:41, 2F
好的，這樣 Pesduo 感覺又能更簡潔一點 ~
※ 編輯: ekids1234 (106.107.244.180 臺灣), 09/21/2019 09:35:13
推
09/21 11:08,
6年前
, 3F
09/21 11:08, 3F
→
09/21 14:48,
6年前
, 4F
09/21 14:48, 4F
→
09/21 14:50,
6年前
, 5F
09/21 14:50, 5F
→
09/21 16:20,
6年前
, 6F
09/21 16:20, 6F
Extract-Min 應該有做類似 pop 的動作沒錯，
我們在討論用 Binary Heap 做 Priority Queue 時
複雜度給他 log(|V|) 就算是包括踢出去 + 調整 Tree 了
→
09/21 18:14,
6年前
, 7F
09/21 18:14, 7F
→
09/21 18:15,
6年前
, 8F
09/21 18:15, 8F
補一下教材的照片
解說有提到，但看他那樣說我還是不知道紀錄的用途
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
推
09/22 00:36,
6年前
, 9F
09/22 00:36, 9F
→
09/22 00:36,
6年前
, 10F
09/22 00:36, 10F
→
09/22 00:36,
6年前
, 11F
09/22 00:36, 11F
→
09/22 00:36,
6年前
, 12F
09/22 00:36, 12F
推
09/23 09:59,
6年前
, 13F
09/23 09:59, 13F