最短路问题的Bellman-Ford算法ppt课件.ppt

《最短路问题的Bellman-Ford算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法最短路问题求解方法Dijkstra算法(荷兰:标号法)逐步逼近算法(Ford(美国)算法):修正标号法路矩阵算法(Floyd(佛洛伊德)算法)逐次逼近算法思想该公式表明，P(1)1j中的第j个分量等于P(0)1j的分量与基本表(权矩阵)中的第j列相应元素路长的最小值，它相当于在v1与vj之间插入一个转接点(v1,v2,…,vn中的任一个，含点v1与vj)后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而P(k)1j中的每一个分量则随着

2、k的增加而呈不增的趋势！v1v2v312-3用于计算带有负权弧指定点v1到其余各点的最短路j=1,2,…,n.k=1,2,…,t≤n.2.计算逐次逼近算法基本步骤j=1,2,…,n.1.令其元素即是v1到vj的最短路长。3.当出现时，v1v2v312-3例计算从点v1到所有其它顶点的最短路解：初始条件为以后按照公式进行迭代。直到得到，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72

3、-35467-24-3342-1400-160240-33-3075-204200利用下标追踪路径基本表空格为无穷大P1j表示从第一个顶点v1到其余各个顶点的最短路,(0)表示迭代次数,表示最多经过中转的次数v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下标追踪路径基本表空格为无穷大最短路问题求解方法Dijkstra算法逐步逼近算法路矩阵算法最短路问题求解方法Dijks

4、tra算法逐步逼近算法路矩阵算法某些问题需要求网络上任意两点间的最短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。这里介绍Floyd在1962年提出的路矩阵法，它可直接求出网络中任意两点间的最短路。Floyd算法(路矩阵法)思想考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉，得只剩vi，vj的一个子网络D0，记wij为弧（vi，vj）的权。在D0中加入v1及D中与vi，vj，v1相关联的弧，得D1，D1中vi到vj的最短路记为,则一定有vivjv1wijFloyd算法(路矩阵

5、法)思想网络D=（V，A，W），令U=(dij)nn，表示D中vi到vj的最短路的长度。dij再在D1中加入v2及D中与vi，vj，v1，v2相关联的弧，得D2，D2中vi到vj的最短路长记为，则有Floyd算法(路矩阵法)思想Floyd算法(路矩阵法)步骤设有有向网络D=（V，A），其权矩阵为A=(aij)n╳n，如下构造路矩阵序列：则n阶路矩阵D(n)中的元素d(n)ij就是vi到vj的最短路的路长。令权矩阵A为初始路矩阵D（0），即令D（0）=A2.依次计算K阶路矩阵D（K）=（d(k)ij）n╳n,k

6、=1,2,…,n，这里路矩阵序列的含义K阶路矩阵D（K）其中的元素表示相应两点间可能以点v1、v2、…、vk为转接点的所有路中路长最短的路的路长。D（0）其中的任一元素表示相应两点间无转接点时最短路路长。一阶路矩阵D（1）其中的元素表示相应两点间可能以点v1为转接点的所有路中路长最短的路的路长；……；为使计算程序化，转接点按顶点下标的顺序依次加入n阶路矩阵D(n)其中的元素d(n)ij就是vi到vj的可能以点v1、v2、…、vn为转接点的所有路中路长最短的路的路长。既是vi到vj的最短路的路长。例求如下交通网络

7、中各对点间最短路路长。该图的权矩阵为：Floyd算法(路矩阵法)算例31025v4v1v2v5v312262448例求如下交通网络中各对点间最短路路长。Floyd算法(路矩阵法)算例31025v4v1v2v5v312262448利用公式发现第一行，第一列元素不变31025v4v1v2v5v312262448利用公式发现第二行，第二列元素不变31025v4v1v2v5v312262448利用公式发现第三行，第三列元素不变31025v4v1v2v5v312262448利用公式发现第四行，第四列元素不变31025v4

8、v1v2v5v31226244831025v4v1v2v5v312262448D(5)中的元素给出相应两点间的最短路，其下标给出最短路个顶点下标,比如：6254已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人，G处60人,问小学应建在哪一个村子，使学生上学最方便（原则①所有人走的总路程最短；②尽