在做题过程中,想过,既然前驱节点可以记录路径,那么后继能不能呢。
那么对于我这种逻辑感不强烈的人,只能动手做了。
在用后继的方式后,将每个点的后继一一的输出后发现了问题,
是这样的,因为在图中,可能一个点所连接的两条边都可能符合条件,比如 1->2, 1->3,2->3这样简单的一个图,如果1->2,1->3的路径都是最短的,那么在更新过程中,1的后继先是2,后来又会变成3,这样,1->2这条边将还原不出来。
那么为什么前驱可以呢,
原因在于在遍历过程中会判断下一个点是否被使用,如果没被使用才会参与运算,这样保证了,某一个点的前驱只更新了一次。而若是后继,则一个点的后继的值至少是更新一次,如果更新大于1次,则先前的点,就无法被还原