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算法可以得到从一个节点到全部节点的最小路径。
网友评论