作者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/cn.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