https://i.imgur.com/Yc7cexk.jpg
不太懂為什麼「令P’為P中去掉P1之所有邊, 再加上P2之路徑 」
這樣就可以證明P1必為shortest path
P1與P2的起終點都是a, b
這樣不就代表兩邊一樣長嗎？
這樣又與P’有什麼關係？
還有想再請教，這個證明是否能用畫圖來理解？
總覺得用文字好像比較難明白解答的意思

題目原本長怎樣...這樣最好有人看的懂= =

https://i.imgur.com/i1MfKM0.jpg抱歉 不知道這樣清楚嗎

畫圖應該沒有比較清楚，題目想證的就是P為ShortestPath(SP）並且subPath皆為SP所以它宣告了兩條subPath一條是SP一條不是所以原來P含有P1（假設不是SP），然後剪下P1貼上（因為皆為a起點b終點所以可以做這個操作）P2造出P’，如此一來便可以說明P’比P還短（因為假設P1不是SP，P2是此時與題目產生矛盾（P為SP），則P1必為SP

有個問題疑惑很久了，證明optimal substructure跟證明greedy choice property差在哪裡呢？知道後者的定義是：若某個選擇是當前最佳選擇，則一定包含在最佳解中，而前者的定義是，最佳解一定有子問題的最佳解建構而成但證明方法好像都是用矛盾證法...

https://i.imgur.com/SoZC4km.jpg附一點圖小講解，希望看得懂。