图Graph--最短路径算法(Shortest Path Algorithm)
发布日期:2021-07-01 03:40:19
浏览次数:3
分类:技术文章
本文共 414 字,大约阅读时间需要 1 分钟。
文章目录
- BFS,DFS 这两种算法主要是针对无权图的搜索算法。
- 针对有权图,图中的每条边都有权重,如何计算两点之间的最短路径(经过的边的权重和最小)呢?
- 像Google地图、百度地图、高德地图这样的地图软件,你只需要输入起始、结束地址,就会给你规划一条最优出行路线。比如最短路线、最少用时、最少红绿灯等等。
1. 算法解析
我们先解决最简单的,最短路线。
- 把地图抽象成图最合适不过了。
- 把每个岔路口看作一个顶点,岔路口与岔路口之间的路看作一条边,路的长度就是边的权重。
- 如果路是单行道,在两个顶点之间画一条有向边;如果路是双行道,就在两个顶点之间画两条方向不同的边。这样,地图就被抽象成一个有向有权图。
这个问题,一个非常经典的算法,是单源最短路径算法(一个顶点到一个顶点)。最出名的莫过于Dijkstra算法了。
算法模板:
- 相关题目:
我的CSDN
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
转载地址:https://michael.blog.csdn.net/article/details/97978966 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月11日 11时30分42秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基于SSM的兼职论坛系统的设计与实现
2021-07-03
基于java的ssm框架就业信息管理系统的设计
2021-07-03
Oracle字符串分隔符替换(替换奇数个或偶数个)
2019-04-30
Oracle 利用 UTL_SMTP 包发送邮件
2019-04-30
Oracle的pfile和spfile的一点理解和笔记
2019-04-30
2021-05-18
2019-04-30
基础架构系列篇-NGINX部署VUE
2019-04-30
基础架构系列篇-系统centos7安装kafka
2019-04-30
在 Vue 中用 Axios 异步请求API
2019-04-30
Mysql 之主从复制
2019-04-30
【NLP学习笔记】中文分词(Word Segmentation,WS)
2019-04-30
对于时间复杂度的通俗理解
2019-04-30
如何输入多组数据并输出每组数据的和?
2019-04-30
行阶梯型矩阵
2019-04-30
JAVA学习笔记6 - 数组
2019-04-30
【学习笔记】Android Activity
2019-04-30
location区段
2019-04-30
linux内存的寻址方式
2019-04-30
how2heap-double free
2019-04-30