数据结构与算法之美
王争
前Google工程师
立即订阅
71367 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

44 | 最短路径:地图软件是如何计算出最优出行路径的?

王争 2019-01-07
基础篇的时候,我们学习了图的两种搜索算法,深度优先搜索和广度优先搜索。这两种算法主要是针对无权图的搜索算法。针对有权图,也就是图中的每条边都有一个权重,我们该如何计算两点之间的最短路径(经过的边的权重和最小)呢?今天,我就从地图软件的路线规划问题讲起,带你看看常用的最短路径算法(Shortest Path Algorithm)。
像 Google 地图、百度地图、高德地图这样的地图软件,我想你应该经常使用吧?如果想从家开车到公司,你只需要输入起始、结束地址,地图就会给你规划一条最优出行路线。这里的最优,有很多种定义,比如最短路线、最少用时路线、最少红绿灯路线等等。作为一名软件开发工程师,你是否思考过,地图软件的最优路线是如何计算出来的吗?底层依赖了什么算法呢?

算法解析

我们刚提到的最优问题包含三个:最短路线、最少用时和最少红绿灯。我们先解决最简单的,最短路线。
解决软件开发中的实际问题,最重要的一点就是建模,也就是将复杂的场景抽象成具体的数据结构。针对这个问题,我们该如何抽象成数据结构呢?
我们之前也提到过,图这种数据结构的表达能力很强,显然,把地图抽象成图最合适不过了。我们把每个岔路口看作一个顶点,岔路口与岔路口之间的路看作一条边,路的长度就是边的权重。如果路是单行道,我们就在两个顶点之间画一条有向边;如果路是双行道,我们就在两个顶点之间画两条方向不同的边。这样,整个地图就被抽象成一个有向有权图。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(49)

  • 五岳寻仙
    课后思考题,自己能想到的。

    1.获取通过某条路的时间:通过某条路的时间与①路长度②路况(是否平坦等)③拥堵情况④红绿灯个数等因素相关。获取这些因素后就可以建立一个回归模型(比如线性回归)来估算时间。其中①②④因素比较固定,容易获得。③是动态的,但也可以通过a.与交通部门合作获得路段拥堵情况;b.联合其他导航软件获得在该路段的在线人数;c.通过现在时间段正好在次路段的其他用户的真实情况等方式估算。

    2.混合公交、地铁和步行时:地铁时刻表是固定的,容易估算。公交虽然没那么准时,大致时间是可以估计的,步行时间受路拥堵状况小,基本与道路长度成正比,也容易估算。总之,感觉公交、地铁、步行,时间估算会比开车更容易,也更准确些。
    2019-01-07
    1
    47
  • 徐凯
    @五岳寻仙的答案太棒了 👏 我感觉每条道路应该还有限速,这个因素也要考察。
    2019-01-07
    15
  • Liam
    有2个疑问:

    1 Dijkstra就是贪心算法吧?
    2 它的解可能不是最优解

    作者回复: Dijkstra实际上可以看做动态规划:)

    2019-01-08
    8
  • 林大涛
    用小顶堆,就是为了确保每个阶段,堆顶的节点都是目前阶段的最短路径的节点。
    2019-02-13
    6
  • 李东勇
    有兴趣的可以看下LeetCode 上这道题: https://leetcode.com/problems/network-delay-time/
    用到的就是Dijkstra 算法
    2019-01-13
    4
  • xuery
    构建优先队列的update函数时,时间复杂度应该是O(n),因为小顶堆查找的时间复杂度是O(n),虽然查找之后向上堆化的时间复杂度时O(logn)
    2019-03-22
    3
  • yongxiang
    王老师,我输入代码运行后,实际出队列的顺序跟图中的不一样,实际(15,0)出队列 在(13,3)出队列前面。我看了代码,应该是修改(25,1)为 (13,3)的时候,小顶堆不会自动更新顺序。需要对22行进行如下修改,更新已经在队列中,又改了dist的Vertex的优先级:
                       if (inQueue[nextVertex.id] == false){
                            queue.add(nextVertex);
                            inQueue[nextVertex.id] = true;
                        }
                        else { // 更新已经在队列中,又改了dist的Vertex的优先级
                            queue.remove(nextVertex);
                            queue.add(nextVertex);
                        }

    作者回复: 嗯嗯 我更新下代码

    2019-01-12
    3
  • mαnajay
    最开始以为是贪心算法, 再看了一遍,才发现优先级队列的作用(拥有类似回溯的功能),按照已添加队列中最短距离进行小顶堆, 每次 poll 的过程中,都有可能将之前已经计算过的顶点再拿出来, 遍历邻接表,重复到目的顶点
    2019-05-18
    2
  • 許敲敲
    类似的python代码也会更新嘛,还不熟悉java的
    2019-01-07
    2
  • Monday
    Dijkstra算法的最后到例子-那张图,各个节点的(0,无), (10,0)等等代表什么意思
    2019-08-30
    1
    1
  • Geek_dddebb
    亲测更新vertex后对象在队列中的位置不变

    作者回复: 代码已经改正,你再看下?;)

    2019-01-07
    1
  • 魏全运
    vertex compareTo有问题吧,怎么没有相等的分支呀?

    作者回复: 有也可以 没有也可以的

    2019-01-07
    1
  • hughieyu
    更新vertex后是否要更新一下对象在优先级队列中的位置,否则会预期更晚弹出优先级队列,会影响查找的速度,除此之外还没有可能出现其他的问题

    作者回复: 会自动更新位置的 相当于堆中更新一个节点的值

    2019-01-07
    1
  • 三年过后
    优先队列代码:
    class PriorityQueue{//构建小顶堆
    Vertex[] nodes;
    private int count;//队列个数
    public PriorityQueue(int v){
    nodes = new Vertex[v+1];//小顶堆,数组从小标1开始,好计算
    this.count = 0;//初始0个元素
    }
    public Vertex poll(){
    Vertex v = nodes[1];//返回堆顶原始
    nodes[1] = nodes[count];//将最后一个元素添加到堆顶,自上而下堆化
    --count;
    heapifyUpToDown(1);//堆顶从上而下堆化
    return v;
    }
    public void add(Vertex vertex){
    nodes[++count] = vertex;
    vertex.i = count;
    heapifyDownToUp(count);//从下往上堆化
    }
    public void update(Vertex vertex){
    //查找,并更新
    nodes[vertex.i].dist = vertex.dist;
    heapifyDownToUp(vertex.i);//从下往上堆化
    }
    public boolean isEmpty(){
    return this.count == 0 ? true : false;
    }
    //自上而下堆化
    private void heapifyUpToDown(int i) {
    while(i<=count){
    int maxPos = i;
    if((i*2)<=count && nodes[maxPos].dist > nodes[i*2].dist) maxPos = 2*i;
    else if((i*2+1)<=count && nodes[maxPos].dist > nodes[i*2+1].dist) maxPos = 2*i+1;
    else if(maxPos == i)break;
    swap(i,maxPos);//交换
    i = maxPos;
    }
    }
    //从下往上堆化
    private void heapifyDownToUp(int i) {
    while (i / 2 > 0 && nodes[i].dist < nodes[i / 2].dist) {
    swap(i,i/2);//交换
    i = i / 2;
    }
    }
    /**
    * 数据交换
    * @param i
    * @param maxPos
    */
    private void swap(int i, int maxPos) {
    nodes[i].i = maxPos;//下标交换记录
    nodes[maxPos].i = i;

    Vertex tmp = nodes[i];
    nodes[i] = nodes[maxPos];
    nodes[maxPos] = tmp;
    }
    }
    2019-11-27
  • 标签
    老师,思考题第二题有没有解题思路啊? 我看了全部评论,没有满意的答案
    2019-11-20
  • 三年过后
    public Vertex poll(){
    --count;
    return nodes[1];//返回堆顶最小元素
    }
    public void add(Vertex v){
    ++count;
    nodes[count] = v;
    heapify(count);//堆化
    }
    //更新dist后,并且从下往上堆化,重新符合堆的定义。时间复杂度O(logn)。
    public void update(Vertex v){
    Vertex vertex = nodes[v.id];
    vertex.dist = v.dist;//更新值
    heapify(v.id);//堆化,自下而上,维护小顶堆
    }
    public boolean isEmpty(){
    if(count ==0) return true;
    return false;
    }
    private void heapify(int i) {
    while(true){
    if(i/2 > 0){
    Vertex vertex = nodes[i];
    Vertex parent = nodes[i/2];//父节点
    if(vertex.dist < parent.dist){//交换节点
    Vertex tmp = nodes[i];
    nodes[i] = nodes[i/2];
    nodes[i/2] = tmp;
    }
    i = i/2;//节点指向父类节点
    }
    }
    }
    2019-10-27
  • 张三
    在图的搜索算法那一节只是提到一句广度优先搜索算法的结果是最短路径,并没有说原因😂

    作者回复: 好像有讲到

    2019-09-03
    2
  • i 星星
    老师,如果这个要是取权重最大该怎么设计呢?

    作者回复: 😅,这个需求就不是最短路径问题了

    2019-08-31
  • Monday
    说实话没感觉到dijkstra算法使用优先级队列的用处,,,
    2019-08-30
  • 美美
    思考题中,计算最短时间的,如果考虑道路情况时动态变化的话,就不能使用Dijkstra算法了,Dijkstra可以看做是动态规划,但是道路情况时动态变换的(根据时间),该问题是不满足无后效性的,所以不能单纯的使用Dijkstra算法。
    2019-08-27
收起评论
49
返回
顶部