最短路问题(Dijkstra算法).ppt

三、计算单源最短路问题(Dijkstra算法)所谓单源是指一个出发顶点,单源最短路问题指的是该顶点至所有可达顶点的最短路径问题。【例题】设计公共汽车线路(3)现有一张县城的城镇地图,图中的顶点为城镇,无向边代表两个城镇间的连通关系,边上的权为公路造价,县城所在的城镇为v0。由于该县的经济比较落后,因此公路建设只能从县城开始规划。规划的要求是所有可达县城的城镇必须建设一条通往县城的汽车线路,该线路的工程的总造价必须最少。输入:n(城市数,1≤n≤20)县城所在的城镇序号v0e(有向边数1≤e≤210)以下e行,每行为3个整数,两个城镇的序号和它们间的公路造价输出:k行,每行为一条通往县城的汽车线路的总造价和该条线路途径的城镇序号拱堡堡迁埂受年嫡继癸榔费趴撞订怂举萍鹃尧卡夕汕轧彼狐强物忠勉才援最短路问题(Dijkstra算法)最短路问题(Dijkstra算法)分析:设G=(V,E)是一个有向图,它的每一条边(U,V)∈E都有一个权W(U,V),在G中指定一个结点V0,要求把从V0到G的每一个结点Vj(VJ∈V)的最短有向路找出来(或者指出不存在从V0到Vj的有向路,即V0不可达Vj)。这个问题即为单源最短路问题。解决单源最短路径的基本思想是把图中所有结点分为两组,每一个结点对应一个距离值第一组:包括已确定最短路径的结点,结点对应的距离值是由v0到此结点的最短路径长度;第二组:包括尚未确定最短路径的结点,结点对应的距离值是v0经由第一组结点(中间结点)至此结点的最短路径长度;我们按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至v0可达的所有结点都包含于第一组。在这个过程中,总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。具体作法是:初始时v0进入第一组,v0的距离值为0;第二组包含其它所有结点,这些结点对应的距离值这样确定(设vi为第二组中的结点)然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm,就要对第二组的各结点的距离值作一次修正(设vi为第二组的结点):若加进vm做中间结点使得v0至vi的路径长度更短(即vi的距离值>vm的距离值+Wmi),则要修改vi的距离(vi的距离值←vm的距离值+Wmi)。修改后再选距离值最小的一个结点加入到第一组中,…。如此进行下去,直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然,这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。匠击革氛谴晾犬椰例朵雁樱彦斤喊筑份淌叠洗恒棵疑癸拭花共价几诚穆簧最短路问题(Dijkstra算法)最短路问题(Dijkstra算法)设n—图的结点数;adj—有向图的相邻矩阵。其中dist—最短路径集合。其中dist[i].pre—在v0至vi的最短路径上,vi的前趋结点序号;dist[i].length—v0至vI的最短路径长度,即vi的距离值;(1≤i≤n)Constn=图的结点数;Typepath=record{路径集合的结点类型}length:real;{距离值}pre:0‥n;{前趋结点序号}end;varadj:array[1‥n,1‥n]ofreal{相邻矩阵}dist:array[1‥n]ofpath;{路径集合}顾尔廊着根卢叫镀孟孵殷牺姜呆曰条历慈汗蓝眶一滩豁翅注杜泼税删极明最短路问题(Dijkstra算法)最短路问题(Dijkstra算法)计算单源最短路径的过程如下:fillchar(adj,sizeof(adj),0);{建立相邻矩阵adj}fori←1tondoforj←1tondoif(i,j)∈Ethenadj[i,j]←wijelseadj[i,j]←∞;fori←1tondo{路径集合初始化}begindist[i].length←adj[v0,i];ifdist[i].length<>∞thendist[i].pre←v0elsedist[i].pre←0;end;{for}adj[v0,v0]←1;{源结点v0进入第一组}repeatmin←∞;u←0;fori←1tondo{从第二组中找距离值最小的结点u}if(adj[i,i]=0)and(dist[i].length<min)thenbeginu←i;min←dist[i].length;end;{then}ifu<>0{第二组中存在一个距离值最小的结点}thenbeginadj[u,u]←1;{结点u进入第一组}fori←1tondo{修正第二组中u可达的结点距离值}if(adj[i,i]=0)and(dist[i].length>dist[u].length+adj[u,i])thenbegindist[i].length←dist[u].length+adj[u,i]