本文共 414 字，大约阅读时间需要 1 分钟。

• BFS,DFS 这两种算法主要是针对无权图的搜索算法。
• 针对有权图，图中的每条边都有权重，如何计算两点之间的最短路径（经过的边的权重和最小）呢？
• 像Google地图、百度地图、高德地图这样的地图软件，你只需要输入起始、结束地址，就会给你规划一条最优出行路线。比如最短路线、最少用时、最少红绿灯等等。

1. 算法解析

我们先解决最简单的，最短路线。

• 把地图抽象成图最合适不过了。
• 把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。
• 如果路是单行道，在两个顶点之间画一条有向边；如果路是双行道，就在两个顶点之间画两条方向不同的边。这样，地图就被抽象成一个有向有权图。

这个问题，一个非常经典的算法，是单源最短路径算法（一个顶点到一个顶点）。最出名的莫过于Dijkstra算法了。

算法模板：

• 相关题目：

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/97978966 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！