CS61B - Lec 30 - Graph 3 - Shortest Paths

Lec 30 - Graph 3 - Shortest Paths

• BFS vs. DFS
• Dijkstra's Algorithm
• Dijkstra's Correctness and Runtime
• A*
• A* Heuristics(启发式学习)

昨天晚上装了下anaconda，准备开始学语音识别了。不得不说把环境调的顺心如意真是最烦的事情，因为好多东西根本不懂只能一直百度，晕头撞向的。

BFS vs. DFS

对比一下BFS和DFS，它们的时空复杂度都相同，并且对所有的graph都适用。唯一有区别的是，DFS对splindly类型的graph，call stack会很庞大；BFS对bushy类型的graph，会建一个庞大的队列。所以各有各应用的领域。

上回书说到，BFS不适合做google map这种的导航路线，因为它并不包含节点的权重，没有距离的信息。比如下图的例子：求s到t的最短路径。应该是直线最短，然而用BST却会输出右图的路径，这是因为包含的edge是最少的，但并没有考虑到每个edge的长度。

Dijkstra’s Algorithm

问题：找到所有节点到s的最短路径。

找完了之后发现是这个样子的：

发现其实最短路径是树状的。这是因为除了根节点，每个节点都只有一条input edge（有另外一条等于绕了一圈又回到了原节点）。另一个事实是：最短路径包含的edge数量，其实是等于vertex数量-1。

看下面的问题。现在找到了最短路径，要设计算法，输出这条最短路径。

方案1：直接无脑DFS。遍历每个节点，如果相邻节点不在最短路径内，将这条路径加到最短路径中。一个节点要保存到它的向邻节点路径的长度，并在遍历到该节点的时候计算到根节点的距离。完全不对，只是遍历了一遍。

方案2：同样是DFS。但是如果发现计算相邻节点到根节点的距离小于之前的路径，就删除之前的路径，重新添加路径。比上一个方法有进步，但仍有bug。CD之间不应该连线，BD之间连线。还是缺少了部分信息。

方案3：Dijkstra算法。在上一个算法的基础上，再加一条规则：遍历相邻节点时，优先遍历到根节点距离小的。解决。

思想是：

• 如果找到了更好的边，用它
• 优先遍历最好的

以下是一个demo，需要用到priorityQueue来实现。

首先设置所有的除0之外的节点distTo = oo。向PQ中插入所有节点，按照distTo从小到大的顺序。

然后计算0的邻节点1和2的disTo和edgeTo，并更新PQ中的距离。

由于2的距离短，优先对2进行操作。removeSmallest，提取出2，然后计算2的邻节点5的disTo和edgeTo，更新距离为16。

接下来，头部是1，那么对1的邻节点2，3，4进行操作。2不受影响因为距离短，更新3和4的距离。

头部是4，所以对4的节点2，5，6进行relax操作。2不变，5的距离更新为9，6的距离计算为10。

然后操作5，没有变化。

然后操作6，更新3的距离为11.

最后操作3，没有什么变化。

最后一行的笔记的意思是：对于weight为正的情况，只要不在PQ上的点，距离就不会有更新的可能了

Dijkstra’s Correctness and Runtime

到这里可以写出算法的大概流程：

从relax具体操作中可以看出来为什么从PQ中去除的点距离不再更新：因为q已经从PQ中去除，所以disTo[q] <= disTo[p]。

总结Dijkstra算法：按照到起点的距离从小到大遍历每个节点，然后对每个结点的edge进行relax操作。

由于以上讨论的PQ去除的节点不被更新，所以每次relax操作是在PQ中寻找更新的节点，这个操作是完全没问题的。但是只是对weight为正的情况，当weight有负数时，不在PQ中的点也有可能需要更新。

分析runtime。由于使用的是PQ结构，所以各种操作都是跟高度有关，复杂度都是O(log V)。

A*

现在再看实际的map问题。如果要得到Denver到NYC的最短距离，那么Dijkstra算法是一个合适的算法么？

它可以得到最短距离，但是问题是这个算法最终会遍历整张地图，非常没有效率。

然后就想了，是不是只要找Denver东边的地点就行了？也就是说，还要引入一个PQ的排序标准。比如下图中的Englewood就比Henderson离Denver近，但是它处于东边，很有可能离NYC近。

A*算法就引入了一个h(v, goal)属性，表示节点v到NYC的估计距离。到根节点的距离d和到目标点的估计距离h相加，共同作为PQ的排序标准。

下面的问题是这个估计距离h该怎么计算呢？

A* Heuristics(启发式学习)

这其实是一个AI问题了。

Happy spring break!

真羡慕他们大二就能上到这么好的课。