[考题] 103年地特资料结构 youtingme PTT批踢踢实业坊

[考题] 103年地特资料结构

楼主: youtingme 2014-12-26 06:52:32

三、请用 Dijkstra 算法找出下图中从S 到T 的最短路径长度：
1.请依序写出过程中逐一加入已被选择的顶点（vertex），起始顶点为S。
请问这题答案唯一吗?
若相邻顶点dist都相同不就好几个答案?
且题目也没说依字母大小加入
这样是只要所有顺序组合都对?
如SEABM...
SEAMB...
SEBAM...
SEBMA...
SEMAB...
SEMBA...
且后面GF DH也都相同
这样就更多可能性组合
阅卷者会从10几个正确答案中一个一个对吗?

作者: fatty3321 2014-12-26 09:26:00

只要法则对，挑出不同路线也行啊

作者: APE36 (PT乡民) 2014-12-26 12:54:00

申论本来就没有一定标准答案，端看老师给分如何再来讨论!!

作者: m121625 (innovation) 2014-12-26 14:33:00

S找到E后只能从E继续找吧,为什么可以跳回去S再找,最小成本扩张树才可跳回原本的点找吧..答案只有一组,还是我错了

作者: fcouple (盲人骑瞎马，夜半临深池) 2014-12-26 14:53:00

答案只会有一组，不管你的点怎么排列。

楼主: youtingme 2014-12-26 19:30:00

加入SE后dist相同的有ABM 所以可选A或B或M还是只能选A?若只能选A这样是只有一组

作者: m121625 (innovation) 2014-12-26 21:48:00

我觉得只能选A除非走到没路,不然往回走就不是最短路径了因为最短路径就是走到目的地最短路,往回走不就越来越长了

继续阅读

[心得] 103年民航特考飞航管制科上榜心得staypure [心得] 103年律师上榜心得iamjoanne [赠送] TKB函授文化行政(洽中)hhalleberry [情报] 考典之公职考试辅导班appter987 [心得] 103年律师考取心得(兼职考生)mythology01 [课业] ABCD参数(含等效电阻)c97252000 [情报] 现在志光周年庆买书七折！dickrandy [赠送] 司律解题书补习班讲义赠送rocking94 [赠送] 书籍summers1001 [心得] 103律师上榜心得jill850421