资源描述：
《最短路径问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最短路径问题基本概念最短路径问题的3种类型单源最短路径问题：找出从每一节点v到某指定节点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。单对节点间的最短路径问题：对于给定节点对u和v，找出从u到v的一条路径。每对节点间的最短路径问题：对于每对节点u和v，找出从u到v的最短路径。可以使用Floyed-Warshall算法解决问题，但时间效率底下，且有不能出现负权回路的苛刻条件。不妨以每个节点为源点运行一次单源算法，以提高时效。松弛技术是单源算法的核心所谓松弛技术，就是反复减小每个节点的实际最短路径的权的
2、上限，直到该上限等于最短路径的权为止。定理：给定有向加权图G=（V，E），设P=为从节点V1到节点Vk的一条路径，对任意i，j有i<=j<=k，设Pij=为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点的父亲。Procinitia
3、llze_single_source(G,s);{foreachv∈V[G]do{d[v]:=∞;f[v]=nil;}d[s]:=0;}松弛一条边（u,v）的过程包括测试是否可通过节点u对目前找出的到v的最短路径进行改进，如果可能则更新d[v]和f[v]，一次松弛操作可以减小最短路长估计d[v]并更新v的父亲f[v]。Procrelax(u,v,w);{ifd[v]>d[u]+w[u,v]then{d[v]:=d[u]+w[u,v];f[v]:=u;}}Dijkstra算法Dijkstra算法解决了有向加权图的最短路径问题，该算法的条
4、件是该图所有边的权值非负，即对于每条边(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队列为空为止。只要
5、图中没有负权边，Dijkstra算法能够顺利完成。如果任何一条边的权值为负，则算法可能得出错误的答案。ProcedureDijstra(G,w,r);{initiallze_single_source(G,r);S:=∮;Q:=V[G];whileQ<>∮do{从最小优先队列Q中取出d值最小的节点u；S:=S∪[u];forv∈adj(u)dorelax(u,v,w);}}Dijkstra算法的执行速度取决于优先队列Q的数据结构。有3种数据结构可供选择：（1）用一维数组实现优先队列，时间复杂度为O（V*V）。使用于规模不大的稠密图。（
6、2）用二叉堆来实现优先队列Q，时间复杂度为O（ElnV），使用于稀疏图。（3）用Fibonacci堆实现优先队列，时间复杂度优化为O（VlnV+E）。但Fibonacci堆的程序实现相当繁琐，程序的实际运行效果不理想，不推荐使用。Dijkstra算法与Prim算法的异同：同：都是属于宽度优先搜索，且优先队列Q都是以距离d为关键字排列的，节点出队后都要进行松弛操作。异：Dijkstra算法中的距离d是节点与源点间最短路长估计值，Prim算法中的距离d是节点连接生成树的最短边长。变形求出最短路的路径对于多条最短路存在的情况，求方案数求次短
7、路径DijkstraP1398Car的旅行路线P1577最佳路线Poj3013BigChristmasTreePoj1135DominoEffect负权回路影响单源最短路径的计算在某些单源最短路径问题中，可能存在权为负的边。如果图G（V,E）不包含由源s可达的负权回路，则对所有v∈Vs，最短路径的权的定义&(s,v)依然正确，即使它是一个负值也是如此。但如果存在一个从s可达的负权回路，最短路径的定义就不能成立了。从s到该回路上的节点不存在最短路径，因为我们总可以顺着找出的“最短”路径再穿过负权回路，从而获得一个权值更小的路径，因此如果
8、从s到v的某路径中存在一个负权回路，我们定义&(s,v)=-∞。Bellman-Ford算法Bellman-Ford算法能在更一般的情况下解决单源点最短路径问题，在该算法中边的权可以为负。Bellman-Ford算法同样
