[考題] 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