找最快的路

每条线距离不同

点跟点用线连起来，你学过了。
可路上还多一样东西。
每条线的距离不一样。
有的路短，
有的路远。
所以在线上写个数字。
那个数字就是距离。
下面点一条路，看看它的距离。

点一条路看距离。(线 = 路 · 数字 = 这条路的距离)

距离不同为什么要紧?
就算是岔口少的路，
要是每一段都远，
整条算下来反而慢。
反过来，岔口多些，
可每段都近，
整条算下来反而快。
所以离开距离，没法挑路。

光按远近不行

前面你看过按远近一圈圈铺开。
一段、两段、三段，
用离起点几段来数。
可那是每条路
都一样是一段时的事。
每条路距离不同了，
段数少的路
不一定就更近。

点这两条路比一比。(段数少的 vs 距离短的 · 不是一回事)

看到了吧? 岔口少的那条路，
按距离反而更远。
光数段数，
就掉这个坑里。
所以我们
不数段数，
而是把距离加起来，
找真正近的路。

先把最近的定下来

那要怎么做?
想想挑眼前最优的那招。
从起点开始，
在距离还没定好的点里，
挑现在最近的那一个，
把它的距离定下来。
最近的那个点
不可能有更短的路，
所以定下来很放心。

点最近的点把它定下来。(每回从没定的里挑最短的)

这就是挑眼前最优。
不是把整张地图一次解完，
而是从现在最近的点起，
一个一个定下来。
定好一个点，
经过它去的
邻居点的距离，
也可能更近了。

把边界往外推

定好的点越多，
就出现一片“距离已定的区域”。
那片区域的边沿就是边界。
每回在边界外头
拉进最近的一个点，
区域就大一个点。
像往静水里扔块石头，
波纹一圈圈散开那样。

点边界外的点把区域养大。(已定区域一个点一个点往外长)

边界一直往外铺，
迟早每个点
都进到已定区域里。
到那会儿，从起点
到任意一个点，
最快的距离
你都知道了。
从近处一步步来，这就是窍门。

小结

把找最快的路收成一行。
每条线距离不同时，
段数少的路不就是快路。
所以光按远近数还不够。
从最近的点把距离定下来，
边界一个点一个点地往外推，
每一刻挑眼前最优，
就找到到每个点的最短距离。

依次点要点来收尾。(距离不同 → 段数不行 → 先定最近 → 推开边界)

地图软件给你找最快的路时，
里头就是这么回事。
从近的地方把距离定下来，
把边界一点点往外推。
眼前最优这条简单规矩，
哪怕在距离各不同的乱路上，
也把最快的答案带给你。