文档介绍：配送线路规划
11/21/2017
P 2
两点间路径问题
T标号(Tentative Label);
P标号(Permanent Label)
11/21/2017
P 3
多点间路径问题
11/21/2017
P 4
4
Floyd算法
Floyd算法是寻找加权图(权值可为负)中任意两个结点间最短路径的算法。
思路:
两结点间的最短路径要么是相邻时最短,要么是以通过几个中间结点为跳板时距离最短。
算法每次以其中一个结点为跳板,如果以该结点为跳板后两结点间路径缩短,则更新这两结点间的路径。
算法执行V次结束,直到测试完每个充当跳板的结点。
11/21/2017
P 5
5
Floyd算法
过程:
Floyd算法采用邻接矩阵W作为图的存储结构,W[i,j]表示结点vi和vj之间的距离(权重);
D(k)记录经历k步后,两点间的路径长,k=0, ..., n ,初始时,W=D(0);
P记录每步更新时结点间经历的中间结点,通过对P矩阵的回溯操作,可得两点间的最短路径,初始时,P为0矩阵。
11/21/2017
P 6
6
Floyd算法
算法第k步的更新规则:
以结点k为跳板,测试通过该结点后,两点间距离是否缩短,若距离不缩短则保留k-1步的结果,D(k)[i,j]=D(k-1)[i,j],
若距离缩短则更新两点间的距离,D(k)[i,j]=D(k-1)[i,k]+D(k-1)[k,j],
即,D(k)[i,j]=min{D(k-1)[i,j], D(k-1)[i,k]+ D(k-1)[k,j]}
如果第k个结点对缩短vi和vj间的路径做出贡献,P[i,j]=k。
11/21/2017
P 7
7
Floyd算法
Floyd算法实例:
图G及算法初始状态(D(0)=W, P=0)如下所示:
8
Floyd算法
9
Floyd算法
矩阵D(4)中,无穷大元素表明其坐标对应的结点间无路径可达,其它元素表示两点间最短路径的长度。最终P指示如何通过回溯得到两结点间的最短路径。例:2到4的最短路径经过3, 则有2-3-4;2到3经过1, 则有2-1-3-4;2到1再无结点(P中对应0),回溯结束,2到4之间最短路径为2-1-3-4,D(2,4)=9
运输问题(略)