15 | 从树到图：如何让计算机学会看地图？

思考1: 如果边权值为负数就不能使用Dijkstra了，因为该算法是贪心算法，即每步都找最优解，在当前步的最优基础上找下一步最优，一定是单调递增的，而出现负权边，这样的前提就不满足了。 而且也不能有带负权值的环，这个样就会一直找当前最优，而且总是满足。 思考2:就在找最小值时返回最小值集合，更新集合内所有点的直连边权值的最小值，且把集合点都加入F。 （by the way这张封面图挺好看的🙂）

Dijkstra好像是基于贪心算法的思想，因为老师用数学归纳法证明了贪心选择可以得到最优，但是出现了负数，就不满足贪心选择了，算法思路应该就变成了动态规划

负数也可以吧，我们取负数的最小值，然后所有边全部加上这个负数的最小值，转换一下不就可以了吗？

黄老师 说的老长了，如果给我们讲个故事 听得会更有趣。 记得 《大话数据结构》里面有说到 广度优先和深度优先算法里，作者 用找东西的例子，广度优先是 到各个地方 比如每个房价 扫一眼，如果没有 再慢慢深入到角落，深度优先 就是 因为有个大概记忆，然后 跟随 记忆 从一个房间 比如抽屉开始 寻找，没有 再去最有可能的角落 找寻，所以 广度优先是 把所有的地方快速扫一眼，没有再慢慢进入小范围 区域，深度优先 就是去指定位置 寻找。 本篇的 Dikstra 大概可以理解：把计算好的节点放入黑箱里，有新的节点加入 只需要与 箱子 的节点连接，然后把新节点与箱子中临近的节点连接起来，计算新节点与临近节点的距离，更新最值，已有的节点间的距离不需要重复计算，总之 Dikstra算法 是没有重复的计算，所以效率会很高，总的计算量会少很多，不像深度优先算法 有大量重复的计算，广度优先算法在添加新节点 时 也会更新已有的计算。 所以Dijstra模块化的思想很节能，它包括 1.寻找MW的最小值或者最大值;2.update更新新节点时，再计算MW的最值。 回答老师的问题：问题一，权限值可以为正为负，例子：跑车游戏中，获胜方为规定时间内奔跑的路程最多，规则为 路线中有不同 奖励，其中有多增加时间的道路，也有减少跑车时间的路线，就是权限值 有正有负。 问题二：多条优先路线，照样可以运用Dijkstra算法，把 多条路线 同时与接入 新节点，然后计算距离，算出MW的值。 有个问题 请教老师：一般地图搜索场景使用Dijkstra多一点还是 动态规划多一点，还是其他算法，地图可以用 百度地图、Google地图 举例。 老师 在专栏里 会谈到 机器学习算法 在生活和产品中的运用吗?

1.纯负数可以，否则不行。留言里那个所有权重加上最小负数绝对值的方法，没有考虑到路径中边的条数是不一样的。 2.如果有多条代价相等的最短路径，需要第二步修改，记录mw[y]=mw[x]+w(x，y)的解

文章最后这段话，”有的时候，边的权重越大越好，比如观光车开过某条路线的车票收入。对于这种情况，Dijkstra 算法就需要调整一下，每次找到最大的 mw，更新邻近结点时也要找更大的值“，应该是有问题的，Dijkstra算法不能用于求最长路径。

1、如果权重全为负值，可以使用Dijstra算法；如果有正有负则不可以，Dijstra算法的基础是通路的权重和是单调递增的，这样才能排除一个个节点。 2、修改方法：求出mv中所有值最小节点，将其一起排除和更新他们的直接连接节点mv值

Dijkstra算法提出的最重要的一点：如果存在一个结点x，到它周边的所有结点中存在一个最小权值的点y，这个点x到点y的最优路径必是该路径。 不可能还存在其他x到y的最小路径，原因是其他的路径在一开始已经大于了该路径。

“第三，假设结点 s 能直接到达的边集合为 M，对于其中的每一条边 m，则把 mw[m]设为 w[s, m]” 我认为这里应该将“每一条边m”，改为“每一个对端节点m”

思考题1： 如果边的权重是负数，运用Dijksta算法得到是任意两个点之间的最大距离，因为负数比较时，绝对值越大则其值越小，因此算法运行后，两个点之间距离的绝对值是这两个点的最大距离。 思考题2： 存在多条路径情况下，算法修改如下： (1)增加一个一维数组，path，存贮从源点到各个节点的最优路径数，path[i]，即表示从源点S到节点i的最优路径数，除源节点path[s]=1外，其余各个节点的路径数都初始化为0。 (2)每当新加入一个节点i，则path[i]的值加1。 (3)每当新加入一个节点i，除了更新权重数组MW，还要对F集合中的节点进行检查，对于F中的某个节点k，如果有mw[i] + mw[i,k] = mw[k]，则说明从源点S到节点k至少存在着两条最优权重的路径，因此path[k]也要加1 最后path数组中即为源点到各节点的最优路径数。