最短路径的问题----单源最短路径

发布于:2021-07-19 22:37:48

算法老师在最短路径问题上讲了很多,在讲了贪心算法之后。紧接着讲最短路径,可以说是一脸懵逼。最*开始复*,总结一下。方法大约有这些。




所谓最短路径,就是指在图中,两个顶点之间经过的边上的权值之和最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点。


首先单源最短路径问题中,我们常见的当迪杰斯特拉算法莫属了。该算法解决的是带权重的有向图的单元最短路径问题,该算法要求所有边的权重都是非负的,该算法在运行过程中需要维持的关键信息是一组结点集合S,从源节点s到该集合中每个节点之间的最短路径已经被找到,算法重复从节点集合{V-S}中选择最短路径估计最小的节点u,将u加入到集合S,然后对所有从u发出的边进行松弛。




其中EXTRACT-MIN(Q)是一个最小优先队列弹出顶端节点的操作。算法前6行作为初始化操作,初始的时候,增加了一个π,算法导论上解释这个标志定义为节点的前驱。比如d[v]=d[u]+w(u,v),这时候咱们的v节点与源节点s是通过u连接的,因为从s直接到v要比s->u->v路径长度要长,所以这时候将π[v]设置为u。从第7行开始,遍历整个优先队列。对所有结点进行松弛操作,找到从s出发到每一个节点的最短路径。因为Dijkstra算法总是选择集合V-S中最轻或者最*的节点来加入到集合S中,该算法使用的是贪心策略。该算法的总运行时间依赖于最小优先队列的实现。




上图是对应不同的最小优先队列结构的时间复杂度。这里面的decrea-key是一个relax操作。


如果遇到了负权值的情况,我们同样有相应的解决方法。Bellman-Ford法。给定带权重的有向图G=(V,E)和权重函数w:


E->R.Bellman-Ford法返回一个布尔值,以表示是否存在一个从源节点到达的权重为负值的环路。如果存在这样的一个环路,将不存在最短路径。该算法通过对边进行松弛操作来渐进的降低从源节点s到每个节点v的最短路径的估值v.d。直到该估计值与实际的最短路径权重相同时为止。




算法前三行对图中所有的d值进行初始化,然后对每条边进行|V|-1次处理,每一次处理都对应的是算法5~7行for循环的一次循环,该循环对图的每条边进行一次松弛操作。我所理解的松弛操作就是对图中的所有顶点找到从源点s到这一个点的最短路径即可。在进行了松弛操作之后,算法8~11行负责检查图中是否存在权重为负值的环路,并返回与之相适应的布尔值。


初始化操作时间复杂度为O(V),对边进行松弛操作的时间复杂度为O(VE),最后的验证操作时间复杂度O(E),所以总的时间复杂度为O(VE)。


单元最短路径的问题还有一个方法就是BFS,这个方法的适用条件是图中边上的权值为1。所以这个可以使用广度优先遍历,因为最短路径的最*最短优先原则,因为权值都是1,所以我们可以得到最*优先的原则,这就是使用BFS而不是DFS的6原因。

相关推荐

最新更新

猜你喜欢