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附一点图小讲解，希望看得懂。