最短路径问题..ppt

差分约束系统 P1389 关系运算图 P1776 工程规划 poj1364 Poj2983 poj3169 最短路径问题 基本概念 最短路径问题的3种类型 单源最短路径问题：找出从每一节点v到某指定节点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对节点间的最短路径问题：对于给定节点对u和v，找出从u到v的一条路径。 每对节点间的最短路径问题：对于每对节点u和v，找出从u到v的最短路径。可以使用Floyed-Warshall算法解决问题，但时间效率底下，且有不能出现负权回路的苛刻条件。不妨以每个节点为源点运行一次单源算法，以提高时效。 松弛技术是单源算法的核心 所谓松弛技术，就是反复减小每个节点的实际最短路径的权的上限，直到该上限等于最短路径的权为止。 定理：给定有向加权图G=（V，E），设P=V1,V2,……,Vk为从节点V1到节点Vk的一条路径，对任意i，j有i=j=k，设Pij=Vi,Vi+1,…,Vj为Vi到Vj的P的子路径，则Pij是从Vi到Vj的一条最短路径。 给定有向加权图G=（V，E），源点为s，则对于所有边（u,v）∈E，有（s，v）=（s，u）+w（u,v）。 松弛技术 对每个节点v∈V，设置一个属性d[v]来描述从源点s到v的最短路径的权的上界，称之为最短路长估计，设置f[v]表示v点的父亲。 Proc initiallze_single_source(G,s); { for each v∈V[G] do {d[v]:=∞;f[v]=nil;} d[s]:=0; } 松弛一条边（u,v）的过程包括测试是否可通过节点u对目前找出的到v的最短路径进行改进，如果可能则更新d[v]和f[v]，一次松弛操作可以减小最短路长估计d[v]并更新v的父亲f[v]。 Proc relax(u,v,w); { if d[v]d[u]+w[u,v] then {d[v]:=d[u]+w[u,v];f[v]:=u;} } Dijkstra算法 Dijkstra算法解决了有向加权图的最短路径问题，该算法的条件是该图所有边的权值非负，即对于每条边(u,v)∈E，w(u,v)=0; Dijkstra算法中设置了一节点集合S，从源节点r到集合S中节点的最终最短路径的权均已确定，即对所有节点v∈S，有d[v]=(r,v)，并设置了最小优先队列Q，该队列包含所有属于V-S的节点（即这些节点尚未确定最短路径的权），且以d值为关键字排列各节点。 初始时，Q包含了除r外的其他节点，这些节点的d值为∞。r进入集合S，d[r]=0。算法反复从Q中取出d值最小的节点u∈V-S，把u插入集合S中，并对u的所有出边进行松弛。这一过程一直进行到Q队列为空为止。 只要图中没有负权边，Dijkstra算法能够顺利完成。如果任何一条边的权值为负，则算法可能得出错误的答案。 Procedure Dijstra(G,w,r); { initiallze_single_source(G,r); S:=∮;Q:=V[G]; while Q∮ do { 从最小优先队列Q中取出d值最小的节点u； S:=S∪[u]; for v∈adj(u) do relax(u,v,w); } } Dijkstra算法的执行速度取决于优先队列Q的数据结构。有3种数据结构可供选择： （1）用一维数组实现优先队列，时间复杂度为O（V*V）。使用于规模不大的稠密图。 （2）用二叉堆来实现优先队列Q，时间复杂度为O（ElnV），使用于稀疏图。 （3）用Fibonacci堆实现优先队列，时间复杂度优化为O（VlnV+E）。但Fibonacci堆的程序实现相当繁琐，程序的实际运行效果不理想，不推荐使用。 Dijkstra算法与Prim算法的异同： 同：都是属于宽度优先有哪些信誉好的足球投注网站，且优先队列Q都是以距离d为关键字排列的，节点出队后都要进行松弛操作。 异：Dijkstra算法中的距离d是节点与源点间最短路长估计值，Prim算法中的距离d是节点连接生成树的最短边长。 变形 求出最短路的路径 对于多条最短路存在的情况，求方案数 求次短路径 Dijkstra P1398 Car的旅行路线 P1577 最佳路线 Poj 3013 Big Christmas Tree Poj 1135 Domino Effect 负权回路影响单源最短路径的计算 在某些单源最短路径问题中，可能存在权为负的边。如果图G（V,E）不包含由源s可达的负权回路，则对所有v∈Vs，最短路径的权的定义(s,v)依然正确，即使它是一个负值也是如此。但如果存在一个从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的节点不存在最短路径，因为