2020年04讲(路线规划).ppt

P *
两点间路径问题
T标号(Tentative Label);
P标号(Permanent Label)
04讲(路线规划)
*
P *
多点间路径问题
04讲(路线规划)
*
P *
*
*
Floyd算法
Floyd算法是寻找加权图(权值可为负)中任意两个结点间最短路径的算法。
思路：
两结点间的最短路径要么是相邻时最短，要么是以通过几个中间结点为跳板时距离最短。
算法每次以其中一个结点为跳板，如果以该结点为跳板后两结点间路径缩短，则更新这两结点间的路径。
算法执行V次结束，直到测试完每个充当跳板的结点。
04讲(路线规划)
*
*
P *
*
*
Floyd算法
过程：
Floyd算法采用邻接矩阵W作为图的存储结构，W[i,j]表示结点vi和vj之间的距离(权重)；
D(k)记录经历k步后，两点间的路径长，k=0, ..., n ，初始时，W=D(0)；
P记录每步更新时结点间经历的中间结点，通过对P矩阵的回溯操作，可得两点间的最短路径，初始时，P为0矩阵。
P *
04讲(路线规划)
*
P *
*
*
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。
04讲(路线规划)
*
P *
*
*
Floyd算法
Floyd算法实例：
图G及算法初始状态(D(0)=W, P=0)如下所示：
04讲(路线规划)
*
*
*
Floyd算法
P *
04讲(路线规划)
*
*
*
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
P *
04讲(路线规划)
*
运输问题(略)
P *
04讲(路线规划)
*
线路问题的引入
1
P *
04讲(路线规划)
*