2.3.3 找到抵达朋友家的最短路径

为了方便阐述找到抵达朋友家的最短路径的Dijkstra算法，我们将地图的结点通过编号进行标注，如图2.17所示。

我们的目的是找到0号结点到4号结点的最短路径，图的复杂度要比前面的例子大很多，仅靠数路径是肯定数不过来的。接下来我们通过图例仔细讲解如何找到最短路径，尽可能快地到达老王家吃饭。最开始结点0到其余结点的距离如表2.15所示。

如表2.15所示，黑色加粗表示我们找到了最短距离，最开始的时候结点0到自身的距离是0，到其他结点的距离是无穷远，使用符号∞表示。

（1）我们从结点0出发，它可以到达结点1和结点7，结点0到结点1的距离是4，到结点7的距离是8，我们更新一下距离表格，如表2.16所示。

因为结点1离结点0比较近，所以我们选择结点1，如图2.18所示。黑色结点代表我们已经找到了到结点0最近的距离。

（2）我们从结点1出发，它可以到达结点2和结点7，结点0经过结点1到达结点7的距离是15，大于结点0直接到结点7的距离8，所以不需要更新路径。结点0经过结点1到达结点2的距离是12，所以我们更新表格，如表2.17所示。

如表2.17所示，现阶段结点0到达结点7的最短距离是8，小于结点0到达结点2的距离12，所以我们选择结点7，如图2.19所示。

（3）我们从结点7出发，它可以到达结点8和结点6，结点0经过结点7到达结点8的距离是15。结点0经过结点7到达结点6的距离是9。所以我们更新表格，如表2.18所示。

如表2.18所示，现阶段结点0到达结点6的距离是9，小于结点0到达结点2的距离12，以及结点0到达结点8的距离15，所以我们选择结点6，如图2.20所示。

（4）我们从结点6出发，它可以到达结点8和结点5，结点0经过结点6到达结点8的距离是15，不小于结点0经过结点7到达结点8的距离15，不需要更新路径。结点0经过结点6到达结点5的距离是11，所以我们更新表格，如表2.19所示。

如表2.19所示，现阶段结点0到达结点5的距离是11，小于结点0到达结点2的距离12，以及结点0到达结点8的距离15，所以我们选择结点5，如图2.21所示。

（5）我们从结点5出发，它可以到达结点4、结点3及结点2，结点0经过结点5到达结点4的距离是21。结点0经过结点5到达结点3的距离是25。结点0经过结点5到达结点2的距离是15，大于结点0经过结点1到达结点2的距离12，不需要更新路径。所以我们更新表格，如表2.20所示。

如表2.20所示，现阶段结点0到达结点2的距离是12，小于结点0到达结点3的距离25，以及结点0到达结点4的距离21和结点0到达结点8的距离15。所以我们选择结点2，如图2.22所示。

（6）我们从结点2出发，它可以到达结点8和结点3，结点0经过结点2到达结点8的距离是14，小于结点0经过结点7到达结点8的距离15，需要更新路径。结点0经过结点2到达结点3的距离是19，小于结点0经过结点5到达结点3的距离25，需要更新距离。所以我们更新表格，如表2.21所示。

如表2.21所示，现阶段结点0到达结点8的距离是14，小于结点0到达结点3的距离19，以及结点0到达结点4的距离21。所以我们选择结点8，如图2.23所示。

（7）我们从结点8出发，发现没有可到达的最短距离的结点，现在我们还剩下两个结点，一个是结点0经过结点2到达结点3，距离是19。另一个是结点0经过结点5到达结点4，距离是21。因为距离结点3较近，所以我们选择结点3，如表2.22所示。

如表2.22所示，我们把结点3加粗，表示我们找到了结点0到达结点3的最短距离19，同时我们的结点更新如图2.24所示。

（8）我们从结点3出发，它可以达到结点4，结点0经过结点3到达结点4的距离是28，大于结点0经过经典5到达结点4的距离21，所以不更新路径，如表2.23所示。

如表2.23所示，我们把结点4加粗，表示我们找到了结点0到达结点4的最短距离21，结点4也是我们需要找的目标结点，所以最终结点0到达结点4的距离是21，我们找到了去老王家的最短路径：结点0—结点7—结点6—结点5—结点4。我们的结点更新如图2.25所示。