无权图的最短路径

复习

　　图上最实用的问题之一，是“从 A 到 B 哪条路最短”。先看最简单的情形：无权图。

　　在无权图里，每条边都一样“贵”，所以“路径短”只取决于经过多少条边。边数最少，就是最短。

　　而我们已经有现成的工具：BFS。上一章说过，BFS 逐层扩张，第一次到达某个节点时，走过的边数就是最少的。所以，在无权图上求最短路，用 BFS 就够了。

　　比如“几度人脉”——你和某人之间隔几个人，正是无权图上的最短路径问题。

　　BFS 不仅知道“有多远”，还能还原“怎么走”。

　　做法是：每当我们从一个节点 u 第一次发现一个新节点 v 时，就记下“v 是从 u 来的”，也就是保存一个前驱。等 BFS 结束后，从目标节点顺着前驱一路往回找，就得到了完整路径，再反过来就是正序。

　　距离用于判断，前驱用于还原。 这两样东西一起，才算真正求出了“最短路径”。

　　可现实中，边往往不是等价的：有的路近，有的路远；有的链路快，有的慢。一旦边带上权重，“边数最少”就不再等于“代价最小”了——走两条短线，可能比走一条长线还便宜。

　　这时 BFS 就无能为力了。我们需要一种能在带权图上求最短路的算法——下一章的 Dijkstra。

思考题 1

　　在无权图里，为什么“边数最少”就是最短？

思考题 2

　　怎样用 BFS 不仅知道距离，还能还原出具体路径？

　　因为无权图中每条边的代价相同，路径的总代价只与经过的边数成正比，边数越少代价越小。所以“边数最少”就等于“最短”。

　　在 BFS 中，每当第一次发现一个新节点时，记录它是从哪个节点到达的，即保存一个前驱指针。搜索结束后，从目标节点沿前驱一路回溯，就能得到完整路径，再将其反转即为正序。

设计师 | 南国微雪