Question

我们时常会面临着对路径选择的决策问题。例如在北京、上海、广州等城市，因其城市面积较大，乘地铁或公交都要考虑从A点到B点，如何换乘到达？比如图7-7-1这样的地铁网图，如果不是专门去做研究，对于刚接触的人来说，都会犯迷糊。

现实中，每个人需求不同，选择方案就不尽相同。有人为了省钱，它需要的是路程最短（定价以路程长短为标准），但可能由于线路班次少，换乘站间距离长等原因并不省时间；而另一些人，为了要赶飞机火车或者早晨上班不迟到，他最大的需求是总时间要短；还有一类人，如老人行动不便，或者上班族下班，忙碌一天累得要死，他们都不想多走路，哪怕车子绕远路耗时长也无所谓，关键是换乘要少，这样可以在车上好好休息一下（有些线路方案换乘两次比换乘三四次耗时还长）。这些都是老百姓的需求，简单的图形可以靠人的经验和感觉，但复杂的道路或地铁网就需要计算机通过算法计算来提供最佳的方案。我们今天就要来研究关于图的最短路径的问题。

图7-7-1

在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。显然，我们研究网图更有实际意义，就地图来说，距离就是两顶点间的权值之和。而非网图完全可以理解为所有的边的权值都为1的网。

我们要讲解两种求最短路径的算法。先来讲第一种，从某个源点到其余各顶点的最短路径问题。

你能很快计算出图7-7-2中由源点v₀到终点v₈的最短路径吗？如果不能，没关系，我们一同来研究看如何让计算机计算出来。如果能，哼哼，那仅代表你智商还不错，你还是要来好好学习，毕竟真实世界的图可没这么简单，人脑是用来创造而不是做枯燥复杂的计算的。好了，我们开始吧。

图7-7-2