最短路问题的Bellman-Ford算法

第1页最短路问题求解方法•Dijkstra算法•逐步逼近算法•路矩阵算法第2页最短路问题求解方法•Dijkstra算法(荷兰:标号法)•逐步逼近算法(Ford(美国)算法):修正标号法•路矩阵算法(Floyd(佛洛伊德)算法)第3页逐次逼近算法思想}{)1(11)(1ijkinikjwPMinP该公式表明，P(1)1j中的第j个分量等于P(0)1j的分量与基本表(权矩阵)中的第j列相应元素路长的最小值，它相当于在v1与vj之间插入一个转接点(v1,v2,…,vn中的任一个，含点v1与vj)后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而P(k)1j中的每一个分量则随着k的增加而呈不增的趋势！v1v2v312-3()(1)11kkjjPP(0)11jjPw第4页用于计算带有负权弧指定点v1到其余各点的最短路}{)1(11)(1ijkinikjwPMinPj=1,2,…,n.k=1,2,…,t≤n.2.计算逐次逼近算法基本步骤(0)11jjPwj=1,2,…,n.1.令(k)(1)11kjjPP其元素即是v1到vj的最短路长。3.当出现时，v1v2v312-3例计算从点v1到所有其它顶点的最短路解：初始条件为0000111213140,2,5,3PPPP以后按照公式进行迭代。直到得到，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1}{)1(11)(1ijkinikjwPMinP)1(1)(1tjtjPP(0)11jjPwv1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij01jP11jP21jP31jP41jP51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-20420002530212303125613611021230312561236613681502123031236531236612366136871412368100212303123653123661236879123681002123031236612368791236810123653利用下标追踪路径}{)1(11)(1ijkinikjwPMinP基本表空格为无穷大P1j表示从第一个顶点v1到其余各个顶点的最短路,(0)表示迭代次数,表示最多经过中转的次数第7页v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij01jP11jP21jP31jP41jP51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-20420002530212303125613611021230312561236613681502123031236531236612366136871412368100212303123653123661236879123681002123031236612368791236810123653利用下标追踪路径}{)1(11)(1ijkinikjwPMinP基本表空格为无穷大第8页最短路问题求解方法•Dijkstra算法•逐步逼近算法•路矩阵算法第9页最短路问题求解方法•Dijkstra算法•逐步逼近算法•路矩阵算法第10页某些问题需要求网络上任意两点间的最短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。这里介绍Floyd在1962年提出的路矩阵法，它可直接求出网络中任意两点间的最短路。Floyd算法(路矩阵法)思想第11页考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉，得只剩vi，vj的一个子网络D0，记ij(0)ij,Aijwvvd当否wij为弧（vi，vj）的权。在D0中加入v1及D中与vi，vj，v1相关联的弧，得D1，D1中vi到vj的最短路记为,则一定有(1)ijd(1)(0)(0)(0)i11jmin,ijijddddvivjv1wijFloyd算法(路矩阵法)思想网络D=（V，A，W），令U=(dij)nn，表示D中vi到vj的最短路的长度。dij第12页再在D1中加入v2及D中与vi，vj，v1，v2相关联的弧，得D2，D2中vi到vj的最短路长记为，则有(2)ijd(2)(1)(1)(1)iji22jmin,ijddddFloyd算法(路矩阵法)思想(1)(0)(0)(0)i11jmin,ijijdddd第13页Floyd算法(路矩阵法)步骤设有有向网络D=（V，A），其权矩阵为A=(aij)n╳n，AvvjiAvvwajijiijij),(,,0),(,如下构造路矩阵序列：则n阶路矩阵D(n)中的元素d(n)ij就是vi到vj的最短路的路长。1.令权矩阵A为初始路矩阵D（0），即令D（0）=A2.依次计算K阶路矩阵D（K）=（d(k)ij）n╳n,k=1,2,…,n，},{)1()1()1()(kkjkikkijkijdddMind这里第14页路矩阵序列的含义K阶路矩阵D（K）其中的元素表示相应两点间可能以点v1、v2、…、vk为转接点的所有路中路长最短的路的路长。D（0）其中的任一元素表示相应两点间无转接点时最短路路长。一阶路矩阵D（1）其中的元素表示相应两点间可能以点v1为转接点的所有路中路长最短的路的路长；……；为使计算程序化，转接点按顶点下标的顺序依次加入n阶路矩阵D(n)其中的元素d(n)ij就是vi到vj的可能以点v1、v2、…、vn为转接点的所有路中路长最短的路的路长。既是vi到vj的最短路的路长。第15页例求如下交通网络中各对点间最短路路长。051250102A2302826042440该图的权矩阵为：Floyd算法(路矩阵法)算例31025v4v1v2v5v312262448第16页例求如下交通网络中各对点间最短路路长。Floyd算法(路矩阵法)算例0051250102D=A230282604244031025v4v1v2v5v3122624480051250102D=A2302826042440(1)(0)(0)(0)i11jmin,ijijdddd利用公式发现第一行，第一列元素不变105125D220213621472302841274133042440031025v4v1v2v5v312262448105125D2202136214723028412741330424400(2)(1)(1)(1)i22jmin,ijijdddd利用公式发现第二行，第二列元素不变255D02136234127221472147023255413344400121257202521731025v4v1v2v5v312262448255D0213621472302325541274133042440012214712572025217(3)(2)(2)(2)i33jmin,ijijdddd利用公式发现第三行，第三列元素不变3D2136323255413341200132421325652147224132604531624031025v4v1v2v5v3122624480021472041270424002214712573D2136323255413341200132421325650214722413260453162404D0213623032552011325/1456202413264133440221472531/5416413245(4)(3)(3)(3)i44jmin,ijijdddd利用公式发现第四行，第四列元素不变31025v4v1v2v5v31226244831025v4v1v2v5v3122624484D021362147230325502401202413264133440221472531/54164132451325/1456D(5)中的元素给出相应两点间的最短路，其下标给出最短路个顶点下标,比如：5D021362147230325502401202413264133440221472531/54164132451325/14566254第22页已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人，G处60人,问小学应建在哪一个村子，使学生上学最方便（原则①所有人走的总路程最短；②尽可能公平。）。最短路问题算例1(选址问题)AGFECB522747163D26第23页005250272074D270627601342106360A最短路问题算例1(选址问题)AGFECB522747163D26第24页21331210525072727074D270627601342106360最短路问题算例1(选址问题)005250272074D270627601342106360A12412521331220527125072727074D27062760134210636021331210525072727074D2706276013421063601241251362132136312132534215215213631632052712650727112707144D7270621271460136114210636012412521331220527125072727074D27062760134210636012412513621324631213254421521521363163205271265072742707144D72706212714601364421063601241251362132136312132534215215213631632052712650727112707144D72706212714601361142106360124125136125472132462573121325132575421457521521363163265775217527521375475605271261550727410270714417D72702691271461036442014151017943012412513621324631213254421521