本文共 414 字,大约阅读时间需要 1 分钟。
- BFS,DFS 这两种算法主要是针对无权图的搜索算法。
- 针对有权图,图中的每条边都有权重,如何计算两点之间的最短路径(经过的边的权重和最小)呢?
- 像Google地图、百度地图、高德地图这样的地图软件,你只需要输入起始、结束地址,就会给你规划一条最优出行路线。比如最短路线、最少用时、最少红绿灯等等。
1. 算法解析
我们先解决最简单的,最短路线。
- 把地图抽象成图最合适不过了。
- 把每个岔路口看作一个顶点,岔路口与岔路口之间的路看作一条边,路的长度就是边的权重。
- 如果路是单行道,在两个顶点之间画一条有向边;如果路是双行道,就在两个顶点之间画两条方向不同的边。这样,地图就被抽象成一个有向有权图。
这个问题,一个非常经典的算法,是单源最短路径算法(一个顶点到一个顶点)。最出名的莫过于Dijkstra算法了。
算法模板:
我的CSDN
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
转载地址:http://uqetf.baihongyu.com/