求网络间两点的距离

最短路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。在求解网络图上节点间最短路径的方法中，用于解决最短路径问题的算法被称作“最短路径算法”。最常用的路径算法有：Dijkstra算法，A*算法，SPFA算法，Bellman-Ford算法，Floyd-Warshall算法，Johnson算法等。迪克斯特拉(Dijkstra)及弗罗伊德(Floyd)算法是其中应用较广的算法。这两种算法中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息在进行图的遍历以搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，直到获得最后的优化路径。面将对这两种算法进行阐述。二、Dijkstra算法、Floyd算法基本步骤:Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。(一)Dijkstra算法:TOC\o"1-5"\h\z令：s={v},i=1,s={v,v, ,v}i 2 3n「 W(v)=0 ...并令：{T()1 -Txv7=g,vesjj1、 对ves，求min{T(v),W(v)+w}=T(v)。j j i ij j2、求min b(v.)}得T(v)，使T(v)=min{T(v)}j k k jvjes3、若v=v则已找到v到v的最短路距离W(v)，否则令i=k从7中删去v转1kn 1n k i

这样经过有限次迭代则可以求出v1到叮勺最短路线’可以用一个流程图来表示:第一步先取W(v)=0意即v到v的距离为0,而TC)是对TC)所赋的初值。111jj第二步利用W(v)已知，根据min (v),W(v)+1jiijj第三步对所有修正后的T(v)求出其最小者T(v)。其对应的点v是v所能一步到达jkk1的点v中最近的一个，由于所有W(u)>0。因此任何从其它点v中转而到达v的通路上的jjk距离都大于v直接到v的距离T(v)，因此T(v)就是v到v的最短距离，所以在算法中令1kkk1kW(v)=T(v)并从s中删去v，若k=n则W(v)=W(v)就是v到v的最短路线,计算结k k k k n 1n束。否则令v.二vk回到第二步，继续运算，直到k=n为止。这样每一次迭代，得到v到一点v的最短距离，重复上述过程直到v=v。1 k kn(二)Floyd算法：Floyd-Warshall算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。

D=「d d>0一；jFloyd算法的基本原理和实现方法为:如果一个矩阵 L其中ij表示i与J间的距离，若i与丿•间无路可通，则dij为无穷大。'与j•间的最短距离存在经过'与j间的k和不经过k两种情况，所以可以令k=1,2,3，，n,n（n为节点数）。检查9与《+dkj的值,在此,♦与dkj分别为目前所知的i到k与k到j的最短距离,因此,S+dkj就是i到j经过k的最短距离。所以，若有dij>dik+dkj，就表示从i出发经k再到j的距离要比原来的i到j距离短,自然把i到丿‘的9重写成dik+dkj。每当一个k搜索完,dij就是目前i到丿‘的最短距离。重复这一过程，最后当查完所有k时，j就为i到'的最短距禺。三、应用：设6个城市v,v, ,v之间的一个公路网（图1）每条公路为图中的边，边上的权数表示该126段公路的长度（单位:百公里）,设你处在城市v，那么从v到v应选择哪一路径使你的费用最1161616计算,先作出该网络的距离矩阵,如下:vv10v251v250L=v321v4g5v5g9Lv6ggvvvv34562ggg159g0810g802510202g520」(0)(0)设W(v)=0,r(v)=8,ves={v,v,v,v,v},1 j 23456(1)第一次迭代①计算r(v),j=2,3,4,5,6如下jr(v)=min存(v),W(v)+w}=min{a,0+5}=522112r(v)=min{r(v),W(v)+w}=min{g,0+2}=231 13r(v)=min^r(v),W(v)+w}=min{a,0+g}=g4 4 1 14r(v)=a,r(v)=a56取min{r(v)}=2=r(v)，令w(v)=r(v)=2j 3 3 3vjes由于k=3H(n=6),令s={v,v,v,v},i=3转(i)2456第二次迭代:①算r(v),j=2,4,5,6如下jr(v)=min{r(v),W(v)+w}=min{5,2+i}=3TOC\o"1-5"\h\z2 3 23r(v)=min{r(v),W(v)+w}=min{8,2+8}=84 3 34r(v)=min{r(v),W(v)+w}=min{i0,2+i0}=i05 3 35r(v)=min{r(v),W(v)+w}=min{a,2+a}=a6 3 36②取min{r(v)}=3=r(v)令w(v)=r(v)=3_ j 2 2 2vesj③由于k=2H(n=6),令s={v,v,v}i=2转⑴456第三次迭代:①算T(v),j=4,5,6如下jT(v)=min{r(v),w(v)+w}=min{8,3+5}=8TOC\o"1-5"\h\z4 2 24T(v)=min{T(v),W(v)+w}=min{10,3+9}=105 2 25r(v)=g6②取min{r(v)}=8=r(v),W(v)=r(v)=8_ j 4 4 4vesj

③由于k=4工(n=6),令S={v,v}i=4转⑴56第四次迭代:①算T(v),j=5,6如下jT(v)=min{T(v),W(v)+w}=min{10,2+8}=10TOC\o"1-5"\h\z5 5 4 45{©8+5}=13T(v)=min{T(v),W(v{©8+5}=13②取min{②取min{T(v)}=j10=T(v),W(v)=T(v)=105 5 5vesj③由于k=5工(n=6),令s={v}转(1)6第五次迭代:①算T(v),j=6如下jT