怎么工作 最短路径 怎么求

每条线的距离不同

用线把点和点连起来，已经学过了。可真实的路上还多一样东西：每条线的距离不同。
有的路短，有的路远，所以在线上写个数字，那个数字就是距离。
点下面的路，看看各自的距离。

点一条路，就能看到它的距离。（线 = 路 · 数字 = 那条路的距离）

距离不同为什么重要？就算经过的岔路少，要是每一段都远，整体也可能更慢。
反过来，就算多经过几个岔路，只要每一段都近，整体也可能更快。
所以选路时不能把距离撇开。

只按远近数步数还不够

前面看过由近及远扩散的办法：一步、两步、三步，按离出发点几步来数。
可那只适用于每条路都正好一步长的情况。
每条路距离不同时，步数少的路不一定更近。

点两条路比一比。（步数少的路 vs 距离短的路 · 并不一样）

经过岔路少的那条路，论距离反而更远。只数步数，就会掉进这个陷阱。
所以不能数步数，而要一路把距离加起来，找出真正近的路。

先定下最近的

那该怎么办？想想挑眼前最好的贪心。
从出发点开始，在距离还没定下来的点里，挑出眼下最近的一个，把它的距离定下来。
只要路的距离都不是负数，到最近的那个点就不可能有更短的路，所以定下来也放心。

点最近的点，把它定下来。（每次都在没定下的点里挑距离最短的）

这就是挑眼前最好的。不是把整张地图都解一遍，而是从眼下最近的点开始，一个个定下来。
定下一个点后，经过它走到的邻居，距离也可能变得更近。
这个办法叫迪杰斯特拉算法。

边界向外扩

定下的点越多，就形成一片“距离已定的区域”，区域的边缘就是边界。
每次从边界外面紧挨着的地方拉进最近的一个点，区域就大一点。
就像往平静的水面扔块石头，水波一圈圈荡开。

点边界外紧挨着的点，区域就会变大。（定下的区域一点一点向外长）

边界一点点向外扩，总有一刻所有的点都进了定下的区域。
那时，从出发点到任何一个点的最快距离就都知道了。由近及远，一步一步来，这就是诀窍。

总结

把找最快的路归成一句话：每条线距离不同时，步数少的路不一定快，所以只按远近数步数还不够。
从最近的点开始定下距离，把边界一点点往外扩，每一刻都挑眼前最好的，就能找到到所有点的最短距离。

按顺序点要点来总结。（距离不同 → 数步数不行 → 先定最近的 → 扩大边界）

地图应用帮你找最快的路时，里面发生的就是这件事：从近处开始定下距离，把边界一点点往外扩。
“挑眼前最好的”这条简单的规则，在距离各不相同的复杂道路上，也能带回最快的答案。