2022.4.3

WEEK11.1 图的最短路径

一、内容

1.迪杰斯特拉算法（Dijkstra Algorithm）

我们上节课讲过BFS，从某种程度说，BFS就是求到源节点的距离的算法，但如果我们加上权重，BFS就不够我们用了。于是我们介绍这种Dijskstra算法(前提是无环的，且权重非负)

带权的图 同样，为了防止循环，我们需要数组记录

其实，根据性质，最后结果应该刚好是一个树
对任意的图，从某节点到任意节点的最短路径树的边数是V-1（假设每个节点都是可达的）

求这个图从A节点开始的最短路径 答案

Relaxation（松弛法）

对于直接用DFS来求最短路径，会得到一个错误的结果，原因之一是我们访问的节点或许不是最好的节点，但一旦访问后就不会再访问，这明显是不好的
于是我们提出松弛法，对于已经访问的节点，我们仍去访问，如果新的路径更短，我们就去更新其路径

如图所示，一开始的距离都是无穷，每一次BFS都会更新节点的路径

最佳优先查找（Best First Search）

我们现在讲另一种更新方法，这既不是DFS，也不是BFS
现在开始按照节点距离起点的距离大小的顺序来考虑（如何选取下一步的）最短路径

假设有这个图 距离A最短的（除了A自己）是C，于是我们选择C 然后再选B，最后到D

这钟算法有贪婪算法的味道

总结算法

我们讲了很多求最短路径的算法，下面我们正式开始讲Dijkstra算法

如图 首先，我们把所有可供选择的节点加入Fringe队列（最小优先队列）中，括号里第一个元素是节点标号，第二个是距开始节点的距离（一开始都为无穷） 信息数组，第一个是距离数组，第二个是记录路径的数组 随后，Fringe队列里的元素出队，如果有小的，换，并更新其信息数组 继续，再出队一个小的元素（最佳优先搜索） 由出队的节点，找到下一个更新的元素 再下，出队最小的元素1 再进行松弛操作（注意这里2也会被访问，虽然没有变化） 进行更新 继续出队最小元素4 进行更新（注意这里5节点原先的值大于新的值，要被更新） 更新

就这样继续出队，直到Fringe队列元素都出完队为止

最后结果 最后结果 伪代码 PQ消耗

我们小结一下，Dijkstra算法可以得到从一个节点到全部节点的最小路径。