最短路问题的Bellman-Ford算法(2)程序.ppt

第1页最短路问题求解方法? Dijkstra 算法?逐步逼近算法?路矩阵算法第2页最短路问题求解方法? Dijkstra 算法(荷兰:标号法)?逐步逼近算法(Ford( 美国)算法):修正标号法?路矩阵算法(Floyd( 佛洛伊德)算法) 第3页逐次逼近算法思想}{ )1(11 )(1 ij kini kjwP Min P?????该公式表明, P (1) 1j中的第 j个分量等于 P (0) 1j的分量与基本表(权矩阵)中的第 j列相应元素路长的最小值, 它相当于在 v 1与v j之间插入一个转接点(v 1,v 2,…,v n中的任一个, 含点 v 1与v j)后所有可能路中的最短路的路长;每迭代一次,就相当与增加一个转接点,而 P (k) 1j中的每一个分量则随着 k的增加而呈不增的趋势! v 1v 2v 312 -3 ( ) ( 1) 1 1 k k j j P P ??(0) 1 1 j j P w ?第4页用于计算带有负权弧指定点 v 1到其余各点的最短路}{ )1(11 )(1 ij kini kjwP Min P?????j =1,2, …,n. k =1,2, …,t≤n .(0) 1 1 j j P w ?j =1,2, …,(k) ( 1) 1 1 k j j P P ??其元素即是 v 1到v j的最短路长。 , v 1v 2v 312 -3 例计算从点v 1到所有其它顶点的最短路解:初始条件为???????? 0 0 0 0 11 12 13 14 0, 2, 5, 3 P P P P ? ????以后按照公式进行迭代。直到得到,迭代停止。 v 1v 2v 3v 4v 6v 5v 8v 7 2 -3 5 467 -24 -3 342 -1}{ )1(11 )(1 ij kini kjwP Min P?????)1(1 )(1 ?? tj tjPP (0) 1 1 j j P w ? v 1v 2v 3v 4v 5v 6v 7v 8 v 8v 7v 6v 5v 4v 3v 2v 1w ij?? 01jP ?? 11jP ?? 21jP ?? 31jP ?? 41jP ?? 51jP v 1v 2v 3v 4v 6v 5v 8v 7 2 -3 5 467 -24 -3 342 -1 40 0 -1 602 40 -33 -307 5 -204 20 0 0253? 02 12303? 1256 136 11 02 12303? 1256 1236 6 1368 15 02 12303? 12365 3 1236 6 1236 6 13687 14 12368 10 02 12303? 12365 3 1236 6 123687 9 12368 10 02 12303? 1236 6 123687 9 12368 10 12365 3利用下标追踪路径}{ )1(11 )(1 ij kini kjwP Min P?????基本表空格为无穷大 P 1j表示从第一个顶点 v 1到其余各个顶点的最短路,(0) 表示迭代次数,表示最多经过中转的次数第7页 v 1v 2v 3v 4v 5v 6v 7v 8 v 8v 7v 6v 5v 4v 3v 2v 1w ij?? 01jP ?? 11jP ?? 21jP ?? 31jP ?? 41jP ?? 51jP v 1v 2v 3v 4v 6v 5v 8v 7 2 -3 5 467 -24 -3 342 -1 40 0 -1 602 40 -33 -307 5 -204 20 0 0253? 02 12303? 1256 136 11 02 12303? 1256 1236 6 1368 15 02 12303? 12365 3 1236 6 1236 6 13687 14 12368 10 02 12303? 12365 3 1236 6 123687 9 12368 10 02 12303? 1236 6 123687 9 12368 10 12365 3利用下标追踪路径}{ )1(11 )(1 ij kini kjwP Min P?????基本表空格为无穷大第8页最短路问题求解方法? Dijkstra 算法?逐步逼近算法?路矩阵算法第9页最短路问题求解方法? Dijkstra 算法?逐步逼