在無向圖中，各邊的權重（距離）為 S−A: 4、S−B: 1、A−B: 2、A−C: 1、B−C: 5、C−T: 3、A−T: 6。以戴克斯特拉演算法求從 S 到 T 的最短路徑時，路徑與長度為下列何者？

正確答案：B. S→B→A→C→T，長度7

戴克斯特拉演算法反覆確定距離尚未確定的頂點中最近的一個，並更新其相鄰頂點的距離。從 S（0）開始，B 以1確定，經由 B 到 A 為 1 + 2 = 3，比直接的4短。確定 A（3）後，C 為 3 + 1 = 4、T 為 3 + 6 = 9；確定 C（4）後，T 更新為 4 + 3 = 7。因此最短路徑為 S→B→A→C→T，長度為7。S→A→C→T（8）因直接走 S−A 而較長，S→B→C→T（9）則因 B−C 的5較大而較長。

• A. 從 S 到 A，經由 B（1 + 2 = 3）比直接走（4）短。
• B. 正確。S→B（1）、B→A（2）、A→C（1）、C→T（3），合計7。
• C. B−C 的權重5較大，經由 A 較短。