迪杰斯特拉算法问题记录
问题1:为什么该列路径长度的最小的项就代表这两点之间的最短路径?
因为目前所有可到达的节点都在一列中列出,其他的未到达的节点一定要通过目前已经可到达的节点才能到达,所以其他的还未到达的节点的路径一定比现在可到达的节点中最小的路径长,所以即使存在另外一条路径可到达目前已经是最短路径的节点,那它也一定比现在这个最小的路径长。
问题2:为什么每次找到最短路径后下一次要用这个最短路径的节点找下一个节点?
这个本质上是一个贪心算法,就是按最有利的方式计算,假如说通过上一个已获得最短路径的节点v2往外走,如果v2可到达v3且比之前到达v3的路径小,那就替换掉原来的到达v3的路径,否则就跳过不替换保持原来的信息。再加上本来我们就是求最短路径,肯定是按目前知道的最小的节点走,总不能再挑个路径大的,得不偿失。