前言：

本文为：https://www.cnblogs.com/lihanyu116/p/14982524.html 补充。

 

 

对于这种情况，我们按照dijsktra和prim的算法的思想，选择点1为起点后。寻找点1的最短边，那么这时我们会选到1--2这条边权为1的边，那么记录下点2为nixt，然后再从点nixt更新并寻找寻找。

那么显然选择点2是错误的。

 

但是我们的这种dijsktra和prim的算法是正确的，为什么呢？

 

我们一步步来模拟一下他运算的过程。

首先我们选择点1后，更新此时的cost[2]=1,cost[3]=2。

我们将二者比较，明显到点2短，记录nixt=2；

然后更新点nixt（2）到点3的值。

重点来了，此时cost[3]仍然等于2，所以此时

cost[j]>map [nixt][j] 即 cost[3]>map [2][3]

这个条件显然是不成立的，所以不去更新。cost[3]还是我们第一次更新的值。

此时从1到3的最短路，为2。

上面那句话可以通俗的理解为：

已经存储的“伪最短路”（cost[j]）和我们寻找的“最新的最短路”(map[nixt][j])比较选择短的一个。

其实对于哪怕像多层图最短路，也是运用的这种思想。

如有不足，请指出，谢谢！