各位好
想請教一下關於 Dijkstra 的 Pseudo Code
https://i.imgur.com/3CO4NP4.png
其實我不知道 S 在這個 Code 的存在意義是什麼
在實作上的確會有 int passed[n] 之類的來記錄是否經過了沒錯
並且在 Relax 的 if 那邊新增確定沒走過
但 Pseduo Code 並沒有對這部分多說明 (我是看林立宇講義 + wiki)
G.adj[u] 理論上也不會去做更動
另外，如果多去記錄有無走過，應該也無法讓程式 複雜度降低
就是多少省一點這樣 ?

抱歉 S的確可以移掉 是我看錯有點亂 你願意的話把我多餘的廢話刪掉吧

是不是證明裡面有用到啊？

Q = V-S不然按照這個code 沒辦法排掉已經決定過的vertex

第五行除了取出最小的點應該也有同時在Q裡去掉？

愈想愈怪 因為實作的時候 只有處理Q和relax而已確實沒有處理S的部分

其實我覺得是操作的時候會用到提醒一下學生XD，不然你看後面的Prim's確實沒有（雖然兩個處理不同問題但概念很像） 我認為追蹤的話應該是掃一遍所有點的狀態，就像原po大大說的一樣

交大江蕙如 Lec12剛好有提到，在45:07之後