求写最短路径算法.由A地到E地,途经B（B1,B2,B3）C（C1,C2,C3）地,基于矩阵乘法求最短路径.我们把求A→E的最短路分解为四个阶段A→B→C→D→E每一个阶段可以用一个矩阵来表示,这个矩阵称

Question

求写最短路径算法.由A地到E地,途经B（B1,B2,B3）C（C1,C2,C3）地,基于矩阵乘法求最短路径.
我们把求A →E 的最短路分解为四个阶段A →B →C→D →E 每一个阶段可以用一个矩阵来表示,这个矩阵称为权矩阵.相邻阶段的路径可以用权矩阵的乘积来表示.但这里的矩阵乘法和普通矩阵乘积运算的区别是:普通矩阵乘积其对应元素是相应元素乘积的代数和,这里把元素相乘改为相加,元素的代数和改为取小运算,如果不同层节点间没有连接,则视它们之间的距离为无穷大.如果是求极大,改为取大运算,此时如果不同层节点间没有连接,则视它们的距离为0.
如下：
由A地到B地的距离可表示为：A[2 5 8]
由B地到C地的权矩阵可表示为
[3,6,5；7,10,8；4,9,6]
因此由A到C的权矩阵为[2,5,8][3,6,5；7,10,8；4,9,6]＝[5,8,7]
因此由A到D的权矩阵为[5,8,7)][7,5；3,4；5,2]＝[11 ,9]
由A→E的权矩阵为：[11 ,9][4,2)]=[15,11]
因此从家里到学校的最短距离为11百米,最近的路径为从A地出发经过B1地C1地D2地到达E地.
下面我们给出基于“矩阵乘法”求解最短路的算法:
第一阶段:计算出图中从起始点到终点最短路的长度.
step1 　划分出该网络图中的层次关系(网络划分为N 层,起点为第一层,终点为第N 层) ;
step2 　依次给出从第i 层到第i + 1 层的权矩阵( i= 1 ,2 ,…,N21) ; (若第i 层有m 个顶点;第i + 1 层有n
个顶点,则从第i 层到第i + 1 层的权矩阵为m *n
阶) .
step3 　按照我们定义的矩阵乘法计算出最短路的
数值.
第二阶段:寻找最短路所经过的中间点.
(利用第一阶段中step2 的数据) 计算出从第i 层到
终点的最短路,对比与i21 层到终点的最短路,从而确
定出第i 层上最短路所经过的顶点( i = 2 ,…,N21) .
依照上面步骤写一个算法,或者根据题目另外写一个也可以.

Answer 1

们把求A →E 的最短路分解为四个阶段A →B →C→D →E 来求解.每一个阶段可以用一个矩阵来表示,这个矩阵称为权矩阵.相邻阶段的路径可以用权矩阵的乘积来表示.但这里的矩阵乘法和普通矩阵乘积运算的区别是:普通矩阵乘积其对应元素是相应元素乘积的代数和,这里把元素相乘改为相加,元素的代数和改为取小运算,如果不同层节点间没有连接,则视它们之间的距离为无穷大. 如果是求极大,改为取大运算,此时如果不同层节点间没有连接,则视它们的距离为0.
如下：
由A地到B地的距离可表示为：A[2 5 8]
由B地到C地的权矩阵可表示为
[3,6,5；7,10,8；4,9,6]
因此由A到C的权矩阵为[2,5,8][3,6,5；7,10,8；4,9,6]＝[5,8,7]
因此由A到D的权矩阵为[5,8,7)][7,5；3,4；5,2]＝[11 ,9]
由A→E的权矩阵为：[11 ,9][4,2)]=[15,11]
因此从家里到学校的最短距离为11百米,最近的路径为从A地出发经过B1地C1地D2地到达E地.

下面我们给出基于“矩阵乘法”求解最短路的算法:
第一阶段:计算出图中从起始点到终点最短路的长度.
step1 　划分出该网络图中的层次关系(网络划分为N 层,起点为第一层,终点为第N 层) ;
step2 　依次给出从第i 层到第i + 1 层的权矩阵( i= 1 ,2 , …, N21) ; (若第i 层有m 个顶点;第i + 1 层有n
个顶点, 则从第i 层到第i + 1 层的权矩阵为m *n
阶) .
step3 　按照我们定义的矩阵乘法计算出最短路的
数值.
第二阶段:寻找最短路所经过的中间点.
(利用第一阶段中step2 的数据) 计算出从第i 层到
终点的最短路, 对比与i21 层到终点的最短路, 从而确
定出第i 层上最短路所经过的顶点( i = 2 , …, N21) .