和龙市建设局网站,jsp网站建设项目实战总结,西安有哪些好玩的,网站开发文档范例单源最短路径问题#xff1a; 给定一个图G (V,E)#xff0c;找出从给定的源点s∈V到其它每个结点v∈V的最短路径。 这样最短路径具有最优子结构性#xff1a;两个结点之间的最短路径的任何子路径都是最短的。 基本概念 负权边#xff1a;权重为负值的边称为负权重的边。 如… 单源最短路径问题 给定一个图G (V,E)找出从给定的源点s∈V到其它每个结点v∈V的最短路径。 这样最短路径具有最优子结构性两个结点之间的最短路径的任何子路径都是最短的。 基本概念 负权边权重为负值的边称为负权重的边。 如果存在负权重的边则有可能存在权重为负值的环路 而造成图中最短路径无定义路径的权重为-∞。 环路最短路不应包含环路。 简单路径不包含环路的路径称为简单路径。 对任何简单路径最多包含|V|-1条边和|V|个结点。 不失一般性假设后续算法寻找的最短路径都不包含环路。 前驱节点v.π 前驱子图,其中 终止时前驱子图是一颗最短路径树包含了从源结点s到每个可以从s到达的结点的一条最短路径 松弛操作Relax 最短路径估计 对于每个结点v维持一个属性v.d记录从源点s到结点v的最短路径权重的上界。 松弛 首先测试一下是否可以对从s到v的最短路径进行改善。如果可以改善则v.d更新为新的最短路径估计值v的前驱v.π更新为新的前驱结点。其中测试指对s到v所经过的最后一个中 间结点u按下列方式计算从s出发 经过u而到达v的路径的权重 将从结点s到结点u之间最短路 径加上结点u到v之间的边的权重 然后与当前的s到v的最短路径估计 v.d进行比较看有没有变小。如果 变小则对v.d和v.π进行更新—— 这一操作就称为“松弛” 三角形不等式 设G(V,E)为一个带权重的有向图其权重函数为 ω:E→R设其源结点为s。那么对于所有的边(u,v)∈E有 上界性质 设G(V,E)为一个带权重的有向图其权重函数为 ω:E→R设其源结点为s。对于所有的结点v∈Vv.d ≥ δ(s,v)并且该不变式在对图G的边进行任何次序的松弛过程中都保持成立而一 旦v.d取得其下界 δ(s,v)后将不再发生变化。 非路径性质 给定一个带权重的有向图G(V,E)其权重函数 为ω:E→R。假定从源结点s到给定点v之间不存在路径则该图在初始化后有 v.d≥δ(s,v)∞ 并且该等式作为不变式一直维持到图G的所有松弛操作结束。 收敛性质 设G(V,E)为一个带权重的有向图其权重函 数为ω:E→R。设s∈V为某个源结点 为图G中的 一条最短路径uv∈V。 如果在对边(u,v)进行松弛操作 之前的某时刻有u.dδ(s,u)则在该松弛操作之后的所有时刻 有v.dδ(s,v) 路径松弛性质 设G(V,E)为一个带权重的有向图其权重函数为ω:E→R。设s∈V为某个源结点考虑从源结点s到结点vk 的任意一条最短路径pv0s。 如果图G进行了一系列边的松弛操作其中包括对 边(v0 ,v1 )、 (v1 ,v2 )、…、 (vk-1 ,vk )按照所列次序而进行的松弛操作则在所有这些松弛操作之后有vk .dδ(s,vk )并且在此之后该等式一直保持。 Bellman-Ford算法 可以有负权边不能有负权环。 可以查出负权环。 时间复杂度O(VE)
