最短路径算法与应用中的问题分析(史上最全路径算法总结)

几种最短路径算法与应用中的问题分析对于一个带权图，求解满足以下条件的最短路径：1，如果权值全部为非负，求一个节点到其它各个节点的最短路径。2，如果权值有正有负，求一个节点到其它各个节点的最短路径。3，如果权值全部为非负，求任意两个节点间的最短路径。4，如果权值有正有负，求任意两个节点间的最短路径。5，不考虑边上的权值，求一个节点到其它各个节点所需经过的最少节点数。6，如果权值非负，求使n个节点连通的最小支撑树的最小花费。7，如果权值非负，求其总长最短的一条过全部节点的初级回路。8，对于无向图，如果权值非负，求从某节点出发经过每条边至少一次最后回到出发点的最短回路9，实际应用中应用广泛的A*算法上面的9个问题基本包含了各种形式和情况下的最短路径。下面我将对上面的9个问题一一讨论。一，非负权值的单源最短路径，解决上述问题1.1，问题的描述：给定一个有向带权图D与源点v,各边上的权值均为非负数，要求找出从v出发到D中其它各顶点的最短路径。对于这样的问题，我们可以运用Dijkstra算法。,2，算法的主要思想是：利用路径长度的递增次序，逐步产生最短路径。首先求出长度最短的一条最短路径，然后参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。3，Dijsktra算法的伪代码描述是：①初始化：S{0};[][0][]vdistjEdgej//dist[j]为v0到节点vj的距离。②求最短路径的长度：dist[]min{[]},{};kdistiiVSSSk③修改：dist[]min{[],[][][]},iVidistidistkEdgekiS对于每一个④判断：若S=V，则算法结束，否则转②算法的复杂度是O(n^2).4，算法应用中的问题分析：虽然在讨论的过程中我们构造的是有向图，但是D算法对于无向图依然适用。这个算法的不足是如果有向图中出现负权值，那么计算结果会出现错误，如图1所示，如果按照D算法v0到v2的最短路径应该是5，而实际上v0到v2的最短路径应该是7-5=2。在有负权值出现时，我们应该用一种全新的算法---Bellman-ford算法。二，任意权值的单源最短路径算法，解决上述问题2.1，问题的描述：给定一个有向带权图D与源点v,各边上的权值为任意实数，要求找出从v出发到D中其它各顶点的最短路径。2，算法的主要思想：此种情况下我们可以用Bellman-ford算法。当图中没有由带负权值的边组成的回路时，有n个顶点的图中任意两个顶点之间如果存在最短路径，此路径最多有n-1条边。Bellman-Ford方法构造一个最短路径长度数组序列dist1[u],dist2[u],…,distn-1[u]，其中，distn-1[u]是从源点v出发最多经过不构成带负长度边回路的n-1条边到达终点u的最短路径长度。算法的最终目的是计算出distn-1[u]。用递推公式distk[u]=min{distk-1[u],min{distk-1[j]+Edge[j][u]}}计算distk[u]，可得从源点v绕过各顶点j，最多经过不构成带负长度边回路的k条边到达终点u的最短路径长度。用它与distk-1[u]比较，取小者作为distk[u]的值，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。3，算法的实现：V0V1V257-5templateclassT,classEvoidBellman-Ford(GraphT,E&G,intv,Edist[],intpath[]){//在有向带权图中有的边具有负的权值。从顶点v//找到所有其他顶点的最短路径。Ew;inti,k,u,n=G.NumberOfVertices();for(i=0;in;i++){//计算dist1[i]dist[i]=G.getWeight(v,i);if(i!=v&&dist[i]maxValue)path[i]=v;elsepath[i]=-1;}for(k=2;kn;k++)//计算dist2[i]到distn-1[i]for(u=0;un;u++)if(u!=v)for(i=0;in;i++){w=G.getWeight(i,u);if(w0&&wmaxValue&&dist[u]dist[i]+w){dist[u]=dist[i]+w;path[u]=i;}}};4，算法在应用过程中的问题分析：虽然该算法是对于有向图进行讨论的，但是对于无向图同样适用。但是对于图中包含有由带负权值的边组成的回路时，如图2所示，如果来回在回路中转圈，则路径的长度会越来越小，从顶点0到顶点2的最短路径长度可达到-。显然此时Bellman-ford算法不适用。三，所有顶点之间的最短路径，解决上述问题3和4.1，问题的描述：已知一个各边权值均大于0的有向带权图，对于每一对节点ViVj,要求出Vi到Vj之间的最短路径与最短路径长度解决这种问题，如果我们利用先前的D算法，轮流以每一个顶点为源点，重复执行Dijkstra算法n次，就可以得到每一对节点之间的最短路径，此时的算法时间复杂度是3O()n，但是这种算法虽然套用比较直接，但是和D算法一样，有向图中不能出现负权值。而对于这种问题，还有一种算法Floyd算法。2，算法的主要思想：Floyd算法仍然使用图的邻接矩阵Edge[n][n]来存储有向带权图。首先初始化Edge[n][n]矩阵，然后逐步尝试在原路径中加入其他顶点作为中间节点，如果增加中间节点后，得到的路径比原来的路径长度减小了，则以此新路径代替原路径，修改矩阵元素，代入新的更短的路径长度，以此类推，这样的增加中间节点，可以得到Floyd算法。3，算法的伪代码：定义一个n阶方阵序列：A(-1),A(0),…,A(n-1).①初始化A(-1)[i][j]=Edge[i][j]；②对于每一对(i,j),求最短路径的长度：A(k)[i][j]=min{A(k-1)[i][j]，A(k-1)[i][k]+A(k-1)[k][j]},k=0,1,…,n-1③判断：若全部的i与j已经遍历完全，则算法结束，否则转②4，算法在应用过程中的问题分析Floyd算法的时间复杂度是O(n3)，这和改进D算法的时间复杂度是相同的，但是Floyd算法在有负权值时依然适用，这一点要优于D算法。四，不考虑边上的权值，求一个节点到其它各个节点所需经过的最少节点数，解决上述问题5这个问题比较简单，我们只需要变通一下，套用一下D算法，可以将边上的权值设为1，则D算法求出的最短路径即是我们需要的经过最少节点数的路径。五，n个节点的连通图之间的最短路径，解决上述问题6.1，问题的描述：在规划建立n个城市之间的通讯网络时，至少要架设n-1条线路，如果在任何两个城市间建造通讯线路的成本已经确定，那么如何使总造价最低？对于这类问题便是最小生成树问题，他要找的便是连通n个节点的代价最小的生成树。2，算法的主要思想：解决最小生成树有两种算法，Kruskal算法和Prim算法Kruskal算法是：设一个有n个顶点的连通网络N={V,E},最初先构造一个只有n个顶点,没有边的非连通图T={V,},图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中;否则将此边舍去，重新选择一条权值最小的边。如此重复下去,直到所有顶点在同一个连通分量上为止。本质是：在保证无回路前提下选n-1条具有最小权值的边。Prim算法是：从连通网络N={V,E}中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0,v),将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在集合U中,而另一个顶点不在集合U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去,直到网络中的所有顶点都加入到生成树顶点集合U中为止。3，算法的伪代码：Kruskal算法的伪代码是：T=;//T是最小生成树的边集合，E是带权无向图的边集合while(T包含的边少于n-1&&E不空){从E中选一条具有最小代价的边(v,w);从E中删去(v,w);如果(v,w)加到T中后不会产生回路,则将(v,w)加入T;否则放弃(v,w);}if(T中包含的边少于n-1条)cout“找不到最小生成树endl;Prim算法的伪代码是：选定构造最小生成树的出发顶点u0;Vmst={u0}，Emst=;while(Vmst包含的顶点少于n&&E不空){从E中选一条边(u,v),uVmst∩vV-Vmst,且具有最小代价(cost);令Vmst=Vmst∪{v},Emst=Emst∪{(u,v)};将新选出的边从E中剔除：E=E-{(u,v)};}if(Vmst包含的顶点少于n)cout不是最小生成树endl;4，算法在应用过程中的问题分析：Prim算法适用于边稠密的网络。Kruskal算法更适合于边稀疏的情形。当各边有相同权值时，由于选择的随意性，产生的生成树可能不唯一。从二者的原理来看，Kruskal算法是基于边的算法，而Prim算法则是基于顶点的。因此对于一个边数很多的图,用Kruskal算法求解并不明智。而顶点与边数之比相对较大的图用Kruskal算法则效率会更高。最小生成树是解决n个节点之间相互连通的重要算法，n个节点相互连通在构建合理的城市交通网络，高效的通信网络等问题方面有重要应用。六，如果权值非负，求其总长最短的一条过全部节点的初级回路。解决问题7。1，问题的描述：给定一个正权完全图，求其总长最短的哈密顿回路。所谓的哈密顿回路便是无向图中一条经过全部节点的初级回路。这个便是图论中非常经典的旅行商问题。2，算法的主要思想：解决旅行商问题的一种比较精确的求解方法是分支与界法。分支与界法的基本思路是：1，首先将边权由小到大排序，初始界d0。2，在边权序列中依次选边进行深探，直到选取n条边，判断是否构成H回路，若是，d0(1)ds，结束。3，继续深探，依次删除当前si中的最长边，加入后面第一条待选边，进行深探，如果它是H回路且d()0isd，则d0()ids作为界。4，退栈过程，不能再深探时需要退栈。如果栈空，结束，其最佳值为d0。否则如果新分支的d()0isd，继续退栈；若d(si)d0,转3.这种搜索过程是在不断的构造分支与确定界值。一旦确定了界值，则对大于等于界值的分支不在搜索，而且最后得到的界值就是问题的最佳解。但是在最坏的情况下，该算法的时间复杂度是O(n!)。因此在实际问题中，我们经常采用近似算法求解问题的近似最优解，近似算法中比较好的是“便宜”算法。便宜算法的基本思路：初始化时T=(1，1);S={2，3，···，n}T是一个不断扩充的初级回路，最初是一个自环。首先我们选取S中与T距离最近的节点j。设（j，t）是相应的边，这时节点j或插入到回路T中t的前面或者插入到其后面，这根据j插入后回路T长度增量的大小而定。即如果w(,)(,1)(,1)(,)(,2)(,2)jtwjtwttwjtwjtwtt，则插入到t与t1之间，否则插入在t与t2之间。七，对于无向图，如果权值非负，求从某节点出发经过每条边至少一次最后回到出发点的最短回路，解决问题8。1，问题描述：邮递员递送报纸与信件，要从邮局出发经过他所管辖的每一条街道最后返回邮局，邮递员希望选择一条最短的传送路径。2，算法的描述：解决中国邮路问题的一个比较好的算法是Edmonds提出的最小权匹配算法。对于图G，如果G不连通，则无解。如果G是欧拉图，则显然欧拉回路就是最优路线。如果G连通，但不是欧拉图，说明图中有度数为奇数的结点。奇点都是成对出现的。对于最简单情况，即2个奇点，设（u，v）。我们可以在G中对（u，v）求最短路径R，构造出新图G’=G∪R。此时G’就是欧拉图。证明：u和v加上了一条边，度加一，改变了奇偶性。而R中其他点度加二，奇偶性不变。由此可知，加一次R，能够减少两个奇点。推广到k个奇点的